HDU2879 HeHe 题解 (思路过程讲解+代码)

思路过程∵x2≡x ( mod n)\because x^2 \equiv x \ (\bmod \ n)∵x2≡x(modn)∴x2−x≡0 ( mod n)\therefore x^2 - x \equiv 0 \ (\bmod \ n)∴x2−x≡0(modn)∴x×(x−1)≡0 ( mod n)\therefore x \times (x - 1) \equiv 0 \ (\bmod \ n)∴x×(x−1)≡0(modn)∴n∣x(x−1)\therefore n \mid x(x-1)∴n∣x(x−1)。两个相邻的整数必定互质 即gcd⁡(x,x−1)1\gcd(x, x - 1) 1gcd(x,x−1)1此时把nnn分解质因数得np1k1p2k2…ptktn p_1^{k_1} p_2^{k_2} \dots p_t^{k_t}np1k1​​p2k2​​…ptkt​​有ttt个不同的质因子∵gcd⁡(x,x−1)1\because \gcd(x, x-1) 1∵gcd(x,x−1)1∴\therefore∴对于nnn的任意一个质数幂次方形式的因子pikip_i^{k_i}piki​​它不可能同时被xxx和x−1x - 1x−1整除 只能二者之一∴\therefore∴对于每一个pikip_i^{k_i}piki​​必定且只能满足以下两个同余方程之一x≡0(modpiki)x \equiv 0 \pmod{p_i^{k_i}}x≡0(modpiki​​)x−1≡0(modpiki)x - 1 \equiv 0 \pmod{p_i^{k_i}}x−1≡0(modpiki​​)即x≡1(modpiki)x \equiv 1 \pmod{p_i^{k_i}}x≡1(modpiki​​)nnn被分解为了ttt个两两互质的模数各个pikip_i^{k_i}piki​​。对于这ttt个同余方程组每一个都有222种独立的选择模pikip_i^{k_i}piki​​为 0 或 1根据中国剩余定理这ttt个方程的每一种组合条件在模nnn的意义下都有且仅有一个唯一解根据乘法原理满足条件的xxx在模nnn意义下的解的总数即为He[n]2t\text{He}[n] 2^tHe[n]2t即He[n]2n的质因子个数\text{He}[n] 2^{\text{n的质因子个数}}He[n]2n的质因子个数然后题目就相当于给定n,mn,mn,m求(2∑i1ni 的质因子个数) mod m(2^{\sum_{i1}^{n} i \ \text{的质因子个数}} )\bmod m(2∑i1n​i的质因子个数)modm线性筛预处理iii的质因子个数(i∈[1,107])(i \in [1, 10^7])(i∈[1,107])∑i1ni 的质因子个数\sum_{i1}^{n} i \ \text{的质因子个数}∑i1n​i的质因子个数这一部分用前缀和进一步优化代码组成快速幂正在做这道题的你应该不至于不会吧但是要注意定义储存结果的变量时应该把初始值设为1 mod 模数1 \bmod \text{模数}1mod模数防止模数为 1 的情况下快速幂结果出错。即int res 1 % mod;不然会WA 80pts线性筛预处理iii的质因子个数 计算前缀和voidget_f(){for(inti1;imaxn;i)isp[i]1;isp[1]0;f[1]0;for(inti2;imaxn;i){if(isp[i]){prime[tot]i;f[i]1;}for(intj1;jtoti*prime[j]maxn;j){isp[i*prime[j]]0;if(i%prime[j]0){//i的质因子包含了prime[j]的所有质因子 所以相乘出来的数的质因子个数与i的相同f[i*prime[j]]f[i];break;}//反之 i和prime[j]互质 此时i和prime[j]的质因子完全不相同 相乘的数包含了它们所有的质因子//所以质因子个数是原数相加f[i*prime[j]]f[i]f[prime[j]];}}for(inti1;imaxn;i){pre[i]pre[i-1]f[i];}}主函数只需要对于多测输入的nnn和mmm计算 power(2, pre[n], m) 即可不多赘述。记得优化输入输出流完整代码#includebits/stdc.husingnamespacestd;#defineintlonglongconstintmaxn1e75;signedf[maxn];signedprime[maxn];inttot;boolisp[maxn];intpre[maxn];intpower(inta,intb,intmod){intbasea%mod;intres1%mod;while(b!0){if(b1)res(res*base)%mod;base(base*base)%mod;b1;}returnres;}voidget_f(){for(inti1;imaxn;i)isp[i]1;isp[1]0;f[1]0;for(inti2;imaxn;i){if(isp[i]){prime[tot]i;f[i]1;}for(intj1;jtoti*prime[j]maxn;j){isp[i*prime[j]]0;if(i%prime[j]0){f[i*prime[j]]f[i];break;}f[i*prime[j]]f[i]f[prime[j]];}}for(inti1;imaxn;i){pre[i]pre[i-1]f[i];}}main(){ios::sync_with_stdio(false);cin.tie(0);intt;get_f();for(cint;t--;cout\n){intn,m;cinnm;coutpower(2,pre[n],m);}return0;}