企石镇仿做网站,山东信达建设有限公司网站,两个网站放在同一个服务器 备案,做网站会什么软件正题
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid7207 题目大意
一个序列aaa#xff0c;和它相同的序列当且仅当能通过以下操作实现相同#xff1a;
将a1a_1a1丢到ana_nan#xff0c;其余的向前移动一位。令所有ai(ai1)%ma_i(a_i1)\%mai(ai1)%m
对于n…正题
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid7207 题目大意
一个序列aaa和它相同的序列当且仅当能通过以下操作实现相同
将a1a_1a1丢到ana_nan其余的向前移动一位。令所有ai(ai1)%ma_i(a_i1)\%mai(ai1)%m
对于n∈[1,N]n\in [1,N]n∈[1,N]求有多少个不同的序列。
1≤T≤100,1≤N,m≤105,∑N≤1061\leq T\leq 100,1\leq N,m\leq 10^5,\sum N\leq 10^61≤T≤100,1≤N,m≤105,∑N≤106 解题思路
根据burnside\text{burnside}burnside引理我们要找所有置换的不动点数量和。
置换总共有n×mn\times mn×m种假设一种为循环位移了xxx步且所有数字加上了yyy。
那么我们有ai≡a(ix)%ny(modm)a_i\equiv a_{(ix)\%n}y\pmod mai≡a(ix)%ny(modm)从一个数开始一直加xxx模nnn我们知道会产生gcd(n,x)\gcd(n,x)gcd(n,x)个环对于每个环来说总共加了ngcd(n,x)\frac{n}{\gcd(n,x)}gcd(n,x)n次yyy最终又走回了起点。
也就是对于这个yyy来说合法的条件当且仅当y×ngcd(n,x)≡1(modm)y\times \frac{n}{\gcd(n,x)}\equiv 1\pmod my×gcd(n,x)n≡1(modm)不难得到合法的yyy的数量就是gcd(m,ngcd(n,x))\gcd(m,\frac{n}{\gcd(n,x)})gcd(m,gcd(n,x)n)。
所以答案就是 1nm∑i0n−1gcd(m,ngcd(n,x))gcd(n,i)\frac{1}{nm}\sum_{i0}^{n-1}\gcd(m,\frac{n}{\gcd(n,x)})^{\gcd(n,i)}nm1i0∑n−1gcd(m,gcd(n,x)n)gcd(n,i) 1nm∑d∣nnφ(nd)gcd(m,nd)d\frac{1}{nm}\sum_{d|n}^n\varphi(\frac{n}{d})\gcd(m,\frac{n}{d})^{d}nm1d∣n∑nφ(dn)gcd(m,dn)d
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#pragma GCC optimize(2)
%:pragma GCC optimize(3)
%:pragma GCC optimize(Ofast)
%:pragma GCC optimize(inline)
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e510,P998244353;
ll T,n,m,cnt,pri[N],phi[N],ans[N];
bool v[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
ll gcd(ll x,ll y)
{return y?gcd(y,x%y):x;}
void Prime(){phi[1]1;for(ll i2;iN;i){if(!v[i])phi[i]i-1,pri[cnt]i;for(ll j1;jcnti*pri[j]N;j){v[i*pri[j]]1;if(i%pri[j]0){phi[i*pri[j]]phi[i]*pri[j];break;}phi[i*pri[j]]phi[i]*phi[pri[j]];}}return;
}
signed main()
{Prime();scanf(%lld,T);while(T--){scanf(%lld%lld,n,m);ll now1,z1;for(ll i1;in;i){zz*m%P;for(ll ji;jn;ji)(ans[j]z*phi[j/i]%P*gcd(m,j/i)%P)%P; }ll invpower(m,P-2)%P;for(ll i1;in;i){ans[i]ans[i]*power(i,P-2)%P*inv%P;printf(%lld%c,ans[i],(in)?\n: );ans[i]0;}}return 0;
}
