高端网站建设哪家公司好,网站外链有什么用,郑州网站托管公司,搭建简单网站解析
很巧妙的题。 关键是要利用好边长为2的整数次幂的性质。 对下标从1开始党极不友好。
首先显然答案就是 2ab2^{ab}2ab -环。 让下标均从0开始。 对于一个点 (i,j)(i,j)(i,j)#xff0c;它原来的内存地址为 i∗2aji*2^aji∗2aj#xff0c;转置后的地址为 j∗2bij*2^bij∗…解析
很巧妙的题。 关键是要利用好边长为2的整数次幂的性质。 对下标从1开始党极不友好。
首先显然答案就是 2ab2^{ab}2ab -环。 让下标均从0开始。 对于一个点 (i,j)(i,j)(i,j)它原来的内存地址为 i∗2aji*2^aji∗2aj转置后的地址为 j∗2bij*2^bij∗2bi。 可以看出其变换就相当于把一个长度为 ababab 的二进制串的前a位放到串尾。 那么环其实就相当于这个置换的等价类的数量。 设 ggcd(a,b),nabgg\gcd(a,b),n\frac {ab} gggcd(a,b),ngab那么本质就是 g 个大小为 n 的环独立进行 [0,n−1][0,n-1][0,n−1] 的轮换。 接下来的反演就不难了。 circle1n∑i1n(2gcd(i,n))g1n∑d∣n2dg∑i1n[gcd(i,n)d]1n∑d∣n2dgφ(nd)circle\frac 1 n\sum_{i1}^n(2^{\gcd(i,n)})^g\frac 1 n\sum_{d|n}2^{dg}\sum_{i1}^n[\gcd(i,n)d]\frac 1 n\sum_{d|n}2^{dg}\varphi(\frac n d)circlen1i1∑n(2gcd(i,n))gn1d∣n∑2dgi1∑n[gcd(i,n)d]n1d∣n∑2dgφ(dn) 预处理欧拉函数和因数复杂度 O(nlnn)−O(d(n)logn)O(n\ln n)-O(d(n)\log n)O(nlnn)−O(d(n)logn)。 不要用 vector ,emplace_back 奇慢
代码
//luogu
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}const int N1e6100;
const int inf1e9;
const int mod1000003;inline ll ksm(ll x,ll k){ll res1;while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n,m;int prime[N],tot,v[N],phi[N];
struct node{int to,nxt;
}p[N*30];
int fi[N],cnt;
inline void add(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}
ll f[N],mi[N];
void init(int n){phi[1]1;for(int i2;in;i){if(!v[i]){phi[i]i-1;prime[tot]i;}for(int j1;jtotprime[j]n/i;j){int nowprime[j];v[now*i]now;if(i%now0){phi[now*i]now*phi[i];break;}else phi[now*i]phi[now]*phi[i];}}for(int i1;in;i){for(int ji;jn;ji) add(j,i);}mi[0]1;for(int i1;in;i) mi[i]mi[i-1]*2%mod; return;
}
int gcd(int x,int y){return y?gcd(y,x%y):x;
}
void work(){int aread(),bread();if(a0||b0){printf(0\n);return;}int ggcd(a,b),n(ab)/g;ll ans(0); for(int ifi[n];i;ip[i].nxt){int dp[i].to;(ansphi[n/d]*mi[g*d])%mod;//printf(T%d f%lld tim%d\n,T,f[T],n/(T/x));}ansans*ksm(n,mod-2)%mod;ans(ksm(2,ab)-ansmod)%mod;printf(%lld\n,ans);
}signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifinit(1000000);int Tread();while(T--) work();return 0;
}
/**/
