HeHe

一、题目

点此看题

$He[n]$为满足$x^2=x\mathrm{m}\mathrm{o}\mathrm{d}n$的个数，求${\prod }_{i=1}^{n}He[i]\mathrm{m}\mathrm{o}\mathrm{d}m$

二、解法

真正的神题

先把所求做一个等价变换： $$x(x-1)=0\mathrm{m}\mathrm{o}\mathrm{d}n$$我们把$n=p_1^{k_1}...p_m^{k_m}$的质因数划分成两个数$p,q$，有$pq=n$，我们令$x=k_{1}p,x-1=k_{2}q$，这样就可以满足上面的条件，但是我们还要满足$k_{1}p-k_{2}q=1$

在$p,q$固定的情况下，显然上式是一个二元一次方程，因为$p$和$q$互质，而且$0\le k_1<q$，运用裴蜀定理可知，一定有解，又因为通解的写法是$k_1=k_1^{\prime }+rq$，那么在$[0,q)$内只有一组解，所以对于任意的$p,q$，有且仅有一种情况。

$p,q$的组数很好算，就是$2^m$（每个质因子划分到哪边）

#include <cstdio> #define ll long long const int M = 1e7+5; int read() { int num=0,flag=1; char c; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1; while(c>='0'&&c<='9')num=(num<<3)+(num<<1)+(c^48),c=getchar(); return num*flag; } int T,n,m,cnt,p[M];bool vis[M]; ll qkpow(ll a,ll b) { ll r=1; while(b>0) { if(b&1) r=r*a%m; a=a*a%m; b>>=1; } return r; } void init(int n) { for(int i=2;i<=n;i++) { if(!vis[i]) p[++cnt]=i; for(int j=1;j<=cnt && i*p[j]<=n;j++) { vis[i*p[j]]=1; if(i%p[j]==0) break; } } } signed main() { T=read(); init(1e7); while(T--) { n=read();m=read(); ll ans=0; for(int i=1;i<=cnt && p[i]<=n;i++) ans+=(n/p[i]); printf("%lld\n",qkpow(2,ans)); } }