poj 2154 Color 欧拉函数优化的ploya计数
函数 优化 poj 计数 欧拉 Color
2023-09-11 14:20:43 时间
枚举位移肯定超时,对于一个位移i。我们须要的是它的循环个数,也就是gcd(i,n),gcd(i,n)个数肯定不会非常多,由于等价于n的约数的个数。
所以我们枚举n的约数。对于一个约数k,也就是循环个数为n/k这种个数有phi[k]种,证明网上有非常多。
所以答案就是 phi[k]*(pow(n,n/k)) (k是n的全部约数)
因为约数会非常大所以不能打表,仅仅能单个算。
再因为最后要除以n,假设做除法就不能直接取模,所以我们在算每一次pow(n,n/k)的时候,都少乘一个n,这样就相当于除法了。
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cstring> using namespace std; const int N=1000000; int quickpow(int m,int n,int k) { int ans=1; while(n) { if(n&1) ans=(ans*m)%k; n=(n>>1); m=(m*m)%k; } return ans; } bool a[N]; int prim[N]; int pp[N]; void Prime() { memset(a, 0, sizeof(a)); int num = 0, i, j; pp[1]=1; for(i = 2; i < N; ++i) { if(!(a[i])) prim[num++]=pp[i]=i; for(j = 0; (j<num && i*prim[j]<N); ++j) { pp[i*prim[j]]=prim[j]; a[i*prim[j]] = 1; if(!(i%prim[j])) break; } } } int phi(int x) { int i,j; int num = x; for(i = 0; prim[i]*prim[i] <= x; i++) { if(x % prim[i] == 0) { num = (num/prim[i])*(prim[i]-1); while(x % prim[i] == 0) { x = x / prim[i]; } } } if(x != 1) num = (num/x)*(x-1); return num; } int main() { Prime(); int cas,n,p; scanf("%d",&cas); while(cas--) { int ans=0; scanf("%d%d",&n,&p); for(int l=1;l*l<=n;l++) { if(n%l==0) { if(l*l==n) { ans+=phi(l)%p*quickpow(n%p,l-1,p); ans%=p; break; } ans+=phi(l)%p*quickpow(n%p,n/l-1,p); ans+=phi(n/l)%p*quickpow(n%p,l-1,p); ans%=p; } } printf("%d\n",ans); } return 0; }
相关文章
- Google Earth Engine(GEE)——关于NDVI_NDWI_NDBI_EVI指数波段运算公式函数的集成和优化(2)
- Google Earth Engine(GEE)——关于NDVI_NDWI_NDBI指数波段运算公式函数的集成和优化(1)
- 如何计算sinc函数的定积分?
- 【BZOJ2226】[Spoj 5971] LCMSum 莫比乌斯反演(欧拉函数?)
- 【MATLAB教程案例16】基于GWO灰狼优化算法的函数极值计算matlab仿真及其他应用
- 【MATLAB教程案例14】基于ACO蚁群优化算法的函数极值计算matlab仿真及其他应用
- 【MATLAB教程案例13】基于SA模拟退火优化算法的函数极值计算matlab仿真及其他应用
- MySQL 函数介绍
- 一维搜索法-- 进退法与黄金分割法求一元二次函数最小值(Java实现)
- Redux优化之JS纯函数(Pure Function)
- 【转载】 tensorflow中 tf.train.slice_input_producer 和 tf.train.batch 函数
- Flink udf的小问题:无参数的udf函数会被优化成常量表达式
- [js高手之路]性能优化技巧 - 缓存与函数重载实战
- 整型数组处理算法(十二)请实现一个函数:最长顺子。[风林火山]
- 手把手教你搭建一个深度网络模型:从输入层-激活函数-损失函数-优化方法-输出层-执行训练