扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
已知数列an的前n项和为sn,满足an≠0,anS（n+1）-a(n+1)Sn=2^（n-1）a(n+1)an,n∈N*（1）求证：Sn=2^（n-1）an；（2）设bn=an/a(n+1),求数列{bn}的前n项和Tn.只要做第2个问题,别复制网上的,不对,求大师做做看
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
不是大师做的：利用（1）的结果.当n>=2时,有Sn+1-Sn=2^(n+1)an+1-2^nan得(2^n-1)an+1=2^(n-1)an,所以bn=(2^n-1)/2^(n-1)=2-1/2^(n-1)它的前n项和为2n-2+1/2^(n-1)
在？bn算的和你一样。算Tn的过程能不能详细点。先采纳你了，麻烦你Tn的过程详细点= =
bn=2-1/2^(n-1)所以Tn=b1+b2+b3+...+bn=
=2-1/2^0+2-1/2^1+2-1/2^2+....+2-1/2^(n-1)
=2n-(1/2^0+1/2^1+1/2^2+...+1/2^(n-1))
=2n-(2-1/2^(n-1))=
=2n-2+1/2^(n-1)
为您推荐：
其他类似问题
扫描下载二维码【codeforces】【比赛题解】#915 Educational CF Round 36
时间： 23:12:36
&&&& 阅读：19
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&虽然最近打了很多场CF，也涨了很多分，但是好久没写CF的题解了。
前几次刚刚紫名的CF，太伤感情了，一下子就掉下来了，不懂你们Div.1。
珂学的那场我只做了第一题……悲伤。
这次的打的还可以，虽然吧没有涨分（因为我是紫色的啊）。
做了前4题，后面3题也比较简单，陆续也做完了。
所以心情好，来写一篇题解！
长度为\(k\)的线段，用若干个长度为\(a_i\)的线段，正好覆盖。（\(a_i|k\)）
给定\(n\)个\(a_i\)，求出最小的\(k/a_i\)，前提是\(a_i|k\)。
1 #include&algorithm&
2 #include&iostream&
3 #include&cstring&
4 #include&string&
5 #include&cstdio&
6 #include&vector&
7 #include&queue&
8 #include&cmath&
9 #include&set&
<span style="color: # #include&map&
<span style="color: # #define ll long long
<span style="color: # #define F(i,a,b) for(int i=(a);i&=(b);++i)
<span style="color: # #define F2(i,a,b) for(int i=(a);i&(b);++i)
<span style="color: # #define dF(i,a,b) for(int i=(a);i&=(b);--i)
<span style="color: # #define dF2(i,a,b) for(int i=(a);i&(b);--i)
<span style="color: # #define eF(i,u) for(int i=h[u];i;i=nxt[i])
<span style="color: # using namespace
<span style="color: # const int INF=<span style="color: #x3f3f3f3f;
<span style="color: # inline int Gcd(int X,int Y){return Y?Gcd(Y,X%Y):X;}
<span style="color: # inline int Max(int X,int Y){return X&Y?Y:X;}
<span style="color: # inline int Min(int X,int Y){return X&Y?X:Y;}
<span style="color: # inline ll Max(ll X,ll Y){return X&Y?Y:X;}
<span style="color: # inline ll Min(ll X,ll Y){return X&Y?X:Y;}
<span style="color: # int n,k,x;
<span style="color: # int ans=<span style="color: #0000000;
<span style="color: # int main(){
<span style="color: #
scanf("%d%d",&n,&k);
<span style="color: #
while(n--) {scanf("%d",&x); if(k%x==<span style="color: #) ans=Min(ans,k/x);}
<span style="color: #
printf("%d",ans);
<span style="color: #
return <span style="color: #;
<span style="color: # }
【B】浏览器
看样例解释猜题意。
对于浏览器顶部的标签，你有这样的操作：关闭这个标签左/右侧的所有标签，把鼠标移到左/右一个标签。
给定标签数目\(n\)，鼠标现在所在的标签\(p\)，问你留下标签区间\([l,r]\)的最少操作次数。
大模拟，注意看左边/右边到底有没有标签。
1 #include&algorithm&
2 #include&iostream&
3 #include&cstring&
4 #include&string&
5 #include&cstdio&
6 #include&vector&
7 #include&queue&
8 #include&cmath&
9 #include&set&
<span style="color: # #include&map&
<span style="color: # #define ll long long
<span style="color: # #define F(i,a,b) for(int i=(a);i&=(b);++i)
<span style="color: # #define F2(i,a,b) for(int i=(a);i&(b);++i)
<span style="color: # #define dF(i,a,b) for(int i=(a);i&=(b);--i)
<span style="color: # #define dF2(i,a,b) for(int i=(a);i&(b);--i)
<span style="color: # #define eF(i,u) for(int i=h[u];i;i=nxt[i])
<span style="color: # using namespace
<span style="color: # const int INF=<span style="color: #x3f3f3f3f;
<span style="color: # inline int Gcd(int X,int Y){return Y?Gcd(Y,X%Y):X;}
<span style="color: # inline int Max(int X,int Y){return X&Y?Y:X;}
<span style="color: # inline int Min(int X,int Y){return X&Y?X:Y;}
<span style="color: # inline ll Max(ll X,ll Y){return X&Y?Y:X;}
<span style="color: # inline ll Min(ll X,ll Y){return X&Y?X:Y;}
<span style="color: # inline int Abs(int X){return X&<span style="color: #?-X:X;}
<span style="color: # int n,p,l,r;
<span style="color: # int main(){
<span style="color: #
scanf("%d%d%d%d",&n,&p,&l,&r);
<span style="color: #
if(l==<span style="color: #&&r==n){puts("<span style="color: #");return <span style="color: #;}
<span style="color: #
if(l==<span style="color: #){printf("%d",Abs(p-r)+<span style="color: #);return <span style="color: #;}
<span style="color: #
if(r==n){printf("%d",Abs(p-l)+<span style="color: #);return <span style="color: #;}
<span style="color: #
printf("%d",Min(Abs(p-r),Abs(p-l))+r-l+<span style="color: #);
<span style="color: #
return <span style="color: #;
<span style="color: # }
【C】数位重排
给定两个数\(a,b\)，求出把\(a\)在十进制下数位重排后不超过\(b\)的最大数，不能有前导零。
1 #include&algorithm&
2 #include&iostream&
3 #include&cstring&
4 #include&string&
5 #include&cstdio&
6 #include&vector&
7 #include&queue&
8 #include&cmath&
9 #include&set&
<span style="color: # #include&map&
<span style="color: # #define ll long long
<span style="color: # #define F(i,a,b) for(int i=(a);i&=(b);++i)
<span style="color: # #define F2(i,a,b) for(int i=(a);i&(b);++i)
<span style="color: # #define dF(i,a,b) for(int i=(a);i&=(b);--i)
<span style="color: # #define dF2(i,a,b) for(int i=(a);i&(b);--i)
<span style="color: # #define eF(i,u) for(int i=h[u];i;i=nxt[i])
<span style="color: # using namespace
<span style="color: # const int INF=<span style="color: #x3f3f3f3f;
<span style="color: # inline int Gcd(int X,int Y){return Y?Gcd(Y,X%Y):X;}
<span style="color: # inline int Max(int X,int Y){return X&Y?Y:X;}
<span style="color: # inline int Min(int X,int Y){return X&Y?X:Y;}
<span style="color: # inline ll Max(ll X,ll Y){return X&Y?Y:X;}
<span style="color: # inline ll Min(ll X,ll Y){return X&Y?X:Y;}
<span style="color: # ll a,b,aa,
<span style="color: # int ca,
<span style="color: # int
<span style="color: # int use[<span style="color: #];
<span style="color: # int bs[<span style="color: #];
<span style="color: # int cs[<span style="color: #];
<span style="color: # void print(){
<span style="color: #
oo=<span style="color: #;
<span style="color: # //
puts("!!");
<span style="color: #
for(int i=i&=<span style="color: #;--i) printf("%d",cs[i]);
<span style="color: # }
<span style="color: # void dfs(int stp,bool deng){
<span style="color: #
if(stp==<span style="color: #) {print(); return;}
<span style="color: #
if(oo) return;
<span style="color: #
for(int i=deng?bs[stp]:<span style="color: #;i&=<span style="color: #;--i){
<span style="color: #
if(stp==ca&&i==<span style="color: #) continue;
<span style="color: #
if(!use[i]) continue;
<span style="color: #
use[i]--; cs[stp]=i;
<span style="color: #
dfs(stp-<span style="color: #,deng?(i==bs[stp]):<span style="color: #);
<span style="color: #
<span style="color: #
<span style="color: # }
<span style="color: # int main(){
<span style="color: #
scanf("%lld%lld",&a,&b); aa=a,bb=b;
<span style="color: #
while(aa) use[aa%<span style="color: #]++,aa/=<span style="color: #,++ while(bb) bs[cb+<span style="color: #]=bb%<span style="color: #,bb/=<span style="color: #,++
<span style="color: #
if(cb&ca){
<span style="color: #
for(int i=<span style="color: #;i&=<span style="color: #;--i) while(use[i]) use[i]--,printf("%d",i);
<span style="color: #
return <span style="color: #;
<span style="color: #
<span style="color: #
dfs(ca,<span style="color: #);
<span style="color: #
return <span style="color: #;
<span style="color: # }
【D】几乎无环图
给定一个有向图，问能否删掉一条边后，这个图变成无环图。\(2\leq n\leq 500,1\leq m\leq min(n(n-1),1000000)\)
先找到一个环（找不到就YES）。
找环用DFS/拓扑排序，我写的时候脑子不好，用了恶心的DFS。
这个环上最多\(n\)条边，对每条边都试一次，看看还有没有环。
为什么要先找到一个环？
拓扑排序/DFS的复杂度是\(O(n+m)\)的。
那么如果直接对每条边试着删除的话，总复杂度\(O((n+m)^2)\)，就T飞了。
先找到一个环的话，总复杂度\(O(n(n+m))\)，能过。
1 #include&algorithm&
2 #include&iostream&
3 #include&cstring&
4 #include&string&
5 #include&cstdio&
6 #include&vector&
7 #include&queue&
8 #include&cmath&
9 #include&set&
<span style="color: # #include&map&
<span style="color: # #define ll long long
<span style="color: # #define F(i,a,b) for(int i=(a);i&=(b);++i)
<span style="color: # #define F2(i,a,b) for(int i=(a);i&(b);++i)
<span style="color: # #define dF(i,a,b) for(int i=(a);i&=(b);--i)
<span style="color: # #define dF2(i,a,b) for(int i=(a);i&(b);--i)
<span style="color: # #define eF(i,u) for(int i=h[u];i;i=nxt[i])
<span style="color: # using namespace
<span style="color: # const int INF=<span style="color: #x3f3f3f3f;
<span style="color: # inline int Gcd(int X,int Y){return Y?Gcd(Y,X%Y):X;}
<span style="color: # inline int Max(int X,int Y){return X&Y?Y:X;}
<span style="color: # inline int Min(int X,int Y){return X&Y?X:Y;}
<span style="color: # inline ll Max(ll X,ll Y){return X&Y?Y:X;}
<span style="color: # inline ll Min(ll X,ll Y){return X&Y?X:Y;}
<span style="color: # int n,m;
<span style="color: # int h[<span style="color: #1],nxt[<span style="color: #0001],to[<span style="color: #0001],
<span style="color: # inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=}
<span style="color: # int used[<span style="color: #1],ret[<span style="color: #1];
<span style="color: # int o,oo,
<span style="color: # int stk[<span style="color: #1],top,pos[<span style="color: #1];
<span style="color: # int fk[<span style="color: #1][<span style="color: #1];
<span style="color: # bool use[<span style="color: #0001];
<span style="color: # int
<span style="color: # void dfs(int u){
<span style="color: # //
printf(" u: %d\n",u);
<span style="color: #
used[u]= stk[++top]=u; pos[u]=
<span style="color: #
<span style="color: #
if(used[to[i]]==<span style="color: #) dfs(to[i]);
<span style="color: #
else{if(used[to[i]]==cnt&&ret[to[i]]==<span style="color: #){/*printf("error : %d -& %d\n",u,to[i]);*/o=pos[to[i]]; return;}}
<span style="color: #
if(o) return;
<span style="color: #
} -- ret[u]=<span style="color: #;
<span style="color: # }
<span style="color: # void dfs2(int u){
<span style="color: # //
printf(" u: %d\n",u);
<span style="color: #
<span style="color: #
eF(i,u) if(!use[i]){
<span style="color: # //
printf("%d -& %d\n",u,to[i]);
<span style="color: #
if(used[to[i]]==<span style="color: #) dfs2(to[i]);
<span style="color: #
else{if(used[to[i]]==cnt&&ret[to[i]]==<span style="color: #){/*printf("error : %d -& %d\n",u,to[i]);*/ooo=<span style="color: #; return;}}
<span style="color: #
if(ooo) return;
<span style="color: #
} ret[u]=<span style="color: #;
<span style="color: # }
<span style="color: # int main(){
<span style="color: #
scanf("%d%d",&n,&m);
<span style="color: #
if(m-<span style="color: #&n*(n-<span style="color: #)/<span style="color: #) {puts("NO"); return <span style="color: #;}
<span style="color: #
if(m&=<span style="color: #) {puts("YES"); return <span style="color: #;}
<span style="color: #
<span style="color: #
F(i,<span style="color: #,m) scanf("%d%d",&x,&y), ins(x,y), fk[x][y]=
<span style="color: #
F(i,<span style="color: #,n){
<span style="color: #
o=<span style="color: #; top=<span style="color: #; cnt=i;
<span style="color: #
if(!used[i]) dfs(i);
<span style="color: #
if(o) {oo=<span style="color: #; break;}
<span style="color: #
<span style="color: #
if(!oo) {puts("YES"); return <span style="color: #;}
<span style="color: # //
F(i,o,top)
<span style="color: # //
printf(",%d",stk[i]); puts("");
<span style="color: #
F(i,o,top){
<span style="color: # //
printf(" %d\n",stk[i]);
<span style="color: #
memset(used,<span style="color: #,sizeof used);
<span style="color: #
memset(ret,<span style="color: #,sizeof ret);
<span style="color: #
ooo=<span style="color: #;
<span style="color: #
if(i!=top) use[fk[stk[i]][stk[i+<span style="color: #]]]=<span style="color: #;
<span style="color: #
else use[fk[stk[i]][stk[o]]]=<span style="color: #;
<span style="color: #
F(j,<span style="color: #,n){
<span style="color: #
<span style="color: #
if(used[j]==<span style="color: #) dfs2(j);
<span style="color: # //
printf("%d %d %d\n",j,used[j],ooo);
<span style="color: # //
puts("====");
<span style="color: #
if(ooo) break;
<span style="color: #
<span style="color: #
if(!ooo) {puts("YES"); return <span style="color: #;}
<span style="color: #
if(i!=top) use[fk[stk[i]][stk[i+<span style="color: #]]]=<span style="color: #;
<span style="color: #
else use[fk[stk[i]][stk[o]]]=<span style="color: #;
<span style="color: #
} puts("NO");
<span style="color: #
return <span style="color: #;
<span style="color: # }
【E】体育课
震惊，Alex发现自己虽然是个ACMer，但是他还是得参加体育期末考！【多么的讽刺啊……】
Alex要算出自己到期末的\(n\)天中，还有多少天能上体育课？
可惜学校时常更改一段时间的有/无上课的状态，可能把一整段区间都变成不上课或者上课。
你需要算出每一次更改后的答案。\(1\leq n\leq 10^9,1\leq q\leq 3\cdot 10^5\)。
离散化，线段树，没什么好说的。
1 #include&algorithm&
2 #include&cstdio&
3 #define F(i,a,b) for(int i=(a);i&=(b);++i)
4 using namespace
5 int n,q;
6 int x[<span style="color: #0001],y[<span style="color: #0001],opt[<span style="color: #0001];
7 int sq[<span style="color: #0001],
8 int siz[<span style="color: #0001];
9 int sz[<span style="color: #97155],dat[<span style="color: #97155],lzy[<span style="color: #97155];
<span style="color: # void build(int i,int l,int r){
<span style="color: #
if(l==r) {sz[i]=siz[l]; return;}
<span style="color: #
int mid=l+r&&<span style="color: #;
<span style="color: #
build(i&&<span style="color: #,l,mid), build(i&&<span style="color: #|<span style="color: #,mid+<span style="color: #,r);
<span style="color: #
sz[i]=sz[i&&<span style="color: #]+sz[i&&<span style="color: #|<span style="color: #];
<span style="color: # }
<span style="color: # void init(){
<span style="color: #
scanf("%d%d",&n,&q);
<span style="color: #
F(i,<span style="color: #,q) scanf("%d%d%d",x+i,y+i,opt+i), sq[++cnt]=x[i]-<span style="color: #, sq[++cnt]=y[i];
<span style="color: #
sort(sq+<span style="color: #,sq+cnt+<span style="color: #);
<span style="color: #
int Cnt=cnt, lst=-<span style="color: #; cnt=<span style="color: #;
<span style="color: #
F(i,<span style="color: #,Cnt) if(sq[i]!=lst) sq[++cnt]=sq[i], lst=sq[i];
<span style="color: #
F(i,<span style="color: #,cnt-<span style="color: #) siz[i]=sq[i+<span style="color: #]-sq[i];
<span style="color: #
F(i,<span style="color: #,q) x[i]=lower_bound(sq+<span style="color: #,sq+cnt+<span style="color: #,x[i]-<span style="color: #)-sq, y[i]=lower_bound(sq+<span style="color: #,sq+cnt+<span style="color: #,y[i])-sq-<span style="color: #;
<span style="color: #
<span style="color: # }
<span style="color: # inline void pushdown(int i){
<span style="color: #
if(lzy[i]==<span style="color: #) dat[i&&<span style="color: #]=sz[i&&<span style="color: #], dat[i&&<span style="color: #|<span style="color: #]=sz[i&&<span style="color: #|<span style="color: #], lzy[i&&<span style="color: #]=lzy[i&&<span style="color: #|<span style="color: #]=<span style="color: #;
<span style="color: #
if(lzy[i]==<span style="color: #) dat[i&&<span style="color: #]=dat[i&&<span style="color: #|<span style="color: #]=<span style="color: #, lzy[i&&<span style="color: #]=lzy[i&&<span style="color: #|<span style="color: #]=<span style="color: #;
<span style="color: #
lzy[i]=<span style="color: #;
<span style="color: # }
<span style="color: # void M(int a,int b,int i,int l,int r,int typ){
<span style="color: #
if(a&=l&&r&=b) {dat[i]=(typ==<span style="color: #?(sz[i]):<span style="color: #); lzy[i]= return;}
<span style="color: #
if(r&a||b&l) return;
<span style="color: #
pushdown(i);
<span style="color: #
int mid=l+r&&<span style="color: #;
<span style="color: #
M(a,b,i&&<span style="color: #,l,mid,typ), M(a,b,i&&<span style="color: #|<span style="color: #,mid+<span style="color: #,r,typ);
<span style="color: #
dat[i]=dat[i&&<span style="color: #]+dat[i&&<span style="color: #|<span style="color: #];
<span style="color: # }
<span style="color: # int main(){
<span style="color: #
<span style="color: #
build(<span style="color: #,<span style="color: #,cnt);
<span style="color: #
F(i,<span style="color: #,q){
<span style="color: #
if(opt[i]==<span style="color: #) M(x[i],y[i],<span style="color: #,<span style="color: #,cnt,<span style="color: #);
<span style="color: #
else M(x[i],y[i],<span style="color: #,<span style="color: #,cnt,<span style="color: #);
<span style="color: #
printf("%d\n",n-dat[<span style="color: #]);
<span style="color: #
<span style="color: #
return <span style="color: #;
<span style="color: # }
【F】海棠数组树的失衡度
给你一棵树，节点有权值，计算\(\sum_{i=1}^n\sum_{j=i}^nI(i,j)\)。
\(I(i,j)\)表示\(i\)到\(j\)的路径上的最大点权-最小点权。
考虑最大最小分开计算，最后最大减最小。
以最大点权为例，如何计算？
假设这个点是\(x\)，考虑计算与\(x\)直接或间接联通的点中，到\(x\)的路径中的点权都不比\(x\)大的点。
通过这些点的个数来计算答案。
可以证明，这些点和\(x\)形成的图是一棵树。
我们以\(x\)为根，\(x\)对答案的贡献是\(val_x\cdot[siz_x^2-\sum_{k=x.son}siz_k^2]\)。
那么怎么找到到\(x\)的路径上的点权都不比\(x\)大的点呢？
考虑按照\(val\)为顺序加入点，用并查集维护连通性，就能算答案了。
1 #include&algorithm&
2 #include&cstdio&
3 #include&cstring&
4 #define F(i,a,b) for(int i=(a);i&=(b);++i)
5 #define F2(i,a,b) for(int i=(a);i&(b);++i)
6 #define dF(i,a,b) for(int i=(a);i&=(b);--i)
7 #define eF(i,u) for(int i=h[u];i;i=nxt[i])
8 int n,a[<span style="color: #00001],I[<span style="color: #00001],siz[<span style="color: #00001];
9 inline bool cmp(int p1,int p2){return a[p1]&a[p2];}
<span style="color: # int h[<span style="color: #00001],nxt[<span style="color: #00001],to[<span style="color: #00001],
<span style="color: # inline void ins(int x,int y){nxt[++tot]=h[x];to[tot]=y;h[x]=}
<span style="color: # bool vis[<span style="color: #00001];
<span style="color: # int fa[<span style="color: #00001];
<span style="color: # int ff(int x){return fa[x]?fa[x]=ff(fa[x]):x;}
<span style="color: # long long
<span style="color: # int main(){
<span style="color: #
scanf("%d",&n);
<span style="color: #
F(i,<span style="color: #,n) scanf("%d",a+i), I[i]=i;
<span style="color: #
int x,y,u; long long
<span style="color: #
F2(i,<span style="color: #,n) scanf("%d%d",&x,&y), ins(x,y), ins(y,x);
<span style="color: #
std::sort(I+<span style="color: #,I+n+<span style="color: #,cmp);
<span style="color: #
F(i,<span style="color: #,n){
<span style="color: #
siz[u=I[i]]=<span style="color: #; tmp=<span style="color: #; vis[u]=<span style="color: #;
<span style="color: #
<span style="color: #
if(vis[to[j]]) siz[u]+=siz[ff(to[j])], tmp+=1ll*siz[ff(to[j])]*siz[ff(to[j])], fa[ff(to[j])]=u;
<span style="color: #
ans+=a[u]*(1ll*siz[u]*siz[u]-tmp);
<span style="color: #
<span style="color: #
memset(fa,<span style="color: #,sizeof fa);
<span style="color: #
dF(i,n,<span style="color: #){
<span style="color: #
siz[u=I[i]]=<span style="color: #; tmp=<span style="color: #; vis[u]=<span style="color: #;
<span style="color: #
<span style="color: #
if(!vis[to[j]]) siz[u]+=siz[ff(to[j])], tmp+=1ll*siz[ff(to[j])]*siz[ff(to[j])], fa[ff(to[j])]=u;
<span style="color: #
ans-=a[u]*(1ll*siz[u]*siz[u]-tmp);
<span style="color: #
<span style="color: #
printf("%lld",ans&&<span style="color: #);
<span style="color: #
return <span style="color: #;
<span style="color: # }
【G】互质数组
我们说数组\(a\)是互质的，当且仅当\(gcd(a_1,a_2,a_3,\cdots,a_n)=1\)。
给定\(k\)，对于每个\(i\;(1\leq i\leq k)\)，求出长度为\(n\)，且其中元素为\(1\)到\(i\)中的正整数的互质数组的个数。
答案对取模，再通过玄学的方式算出最终答案。
容斥+数论（莫比乌斯函数）。
考虑容斥，先计算所有的个数，再扣掉元素是\(2\)的倍数的数组的个数，\(3\)的倍数……
\(4\)的倍数不用扣掉，因为\(2\)已经扣掉过了。
但是\(6\)的倍数被\(2\)和\(3\)扣掉了两遍，要加回来。
对于是\(x\)的倍数，容斥系数就是\(\mu(x)\)——\(x\)的莫比乌斯函数。
对于\(i\)的答案，是\(\sum_{j=1}^{i}\mu(j)(\left\lfloor\frac{i}{j}\right\rfloor)^n\)。
对于每个\(i\)，我们使用差分的技巧统计答案。
1 #include&cstdio&
2 #define Mod
3 int n,k,A
4 bool isnprime[<span style="color: #00001]={<span style="color: #,<span style="color: #};
5 int mobius[<span style="color: #00001]={<span style="color: #,<span style="color: #};
6 int primes[<span style="color: #00001],
7 int ans[<span style="color: #00001];
8 int pows[<span style="color: #00001];
9 void Mobius(int num){
<span style="color: #
for(int i=<span style="color: #;i&=++i){
<span style="color: #
if(!isnprime[i])
<span style="color: #
primes[++pnum]=i, mobius[i]=-<span style="color: #;
<span style="color: #
for(int j=<span style="color: #;j&=pnum&&i*primes[j]&=++j){
<span style="color: #
isnprime[i*primes[j]]=<span style="color: #;
<span style="color: #
if(i%primes[j]==<span style="color: #) break;
<span style="color: #
mobius[i*primes[j]]=-mobius[i];
<span style="color: #
<span style="color: #
<span style="color: # }
<span style="color: # inline int Pow(int base,int exp){
<span style="color: #
int sum=<span style="color: #;
<span style="color: #
while(exp){
<span style="color: #
if(exp&<span style="color: #) sum=(long long)sum*base%M
<span style="color: #
base=(long long)base*base%M exp&&=<span style="color: #;
<span style="color: #
<span style="color: # }
<span style="color: # int main(){
<span style="color: #
scanf("%d%d",&n,&k);
<span style="color: #
Mobius(k);
<span style="color: #
pows[<span style="color: #]=<span style="color: #;
<span style="color: #
for(int i=<span style="color: #;i&=k;++i) pows[i]=Pow(i,n);
<span style="color: #
for(int i=<span style="color: #;i&=k;++i){
<span style="color: #
if(!mobius[i]) continue;
<span style="color: #
for(int j=<span style="color: #;j*i&=k;++j){
<span style="color: #
ans[j*i]-=mobius[i]*pows[j-<span style="color: #];
<span style="color: #
ans[j*i]+=mobius[i]*pows[j];
<span style="color: #
ans[j*i]=((ans[j*i]%Mod)+Mod)%M
<span style="color: #
<span style="color: #
<span style="color: #
for(int i=<span style="color: #;i&=k;++i) ans[i]=(ans[i-<span style="color: #]+ans[i])%Mod, Ans=(Ans+(ans[i]^i))%M
<span style="color: #
printf("%d",Ans);
<span style="color: #
return <span style="color: #;
<span style="color: # }
&标签：&&&&&&&&&&&&&&&&&&&&&&&&&&&原文：https://www.cnblogs.com/PinkRabbit/p/8290384.html
教程昨日排行
&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！