首页 > 代码库 > HDU 5407 CRB and Candies(LCM +最大素因子求逆元)
HDU 5407 CRB and Candies(LCM +最大素因子求逆元)
【题目链接】click here~~
【题目大意】求LCM(Cn0,Cn1,Cn2....Cnn)%MOD 的值
【思路】来图更直观:
这个究竟是怎样推出的,说实话。本人数学归纳大法没有推出来,幸得一个大神给定愿文具体证明,点击这里:click here~~
代码:
#include <bits/stdc++.h> using namespace std; const int N=1e6+10; const int MOD=1e9+7; typedef long long LL; LL p[N]; LL arr[N]; bool ok(int n) //推断n是不是仅仅有一个质因子,p[n]表示n最大的质因子。 { int t=p[n]; while(n%t==0&&n>1) n/=t; return n==1; } LL poww(LL a,LL b) { LL res=a,ans=1; while(b) { if(b&1) ans=res*ans%MOD; res=res*res%MOD; b>>=1; } return ans; } LL niyuan(LL a) /// 求逆元 { return poww(a,MOD-2); } inline LL read() { int c=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){c=c*10+ch-‘0‘;ch=getchar();} return c*f; } void init() { for(int i=1; i<N; ++i) p[i]=i; for(int i=2; i<N; ++i) if(p[i]==i) { for(int j=i+i; j<N; j+=i) p[j]=i; } arr[0]=1; for(int i=1; i<N; ++i)//求LCM { if(ok(i)) arr[i]=arr[i-1]*p[i]%MOD; else arr[i]=arr[i-1]; } } int main() { init(); int t;t=read(); while(t--) { int n;n=read(); LL ans=arr[n+1]*niyuan(n+1)%MOD;//由欧拉定理a^(p-1) mod p = 1 p是质数 所以a的逆元是a^{p-2} printf("%lld\n",ans); } return 0; }
HDU 5407 CRB and Candies(LCM +最大素因子求逆元)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。