51 nod 1189 阶乘分数
分类：数论
阶乘素因子分解
题目链接： 题目思路： 1/n! = 1/x +1/y
==> n! * (x + y) = x * y（右边通分，，然后转化）
==> n!^2 = (x – n!)*(y – n!)（左右两边加上n方）
==> a = b * c ,a = n!^2 ,b = x – n! ,c = y – n!
;LL;const int mod = 1e9+7;const int maxn=1e6+5;bool prime[maxn];int p[maxn/10];int k;void isprime(){k=0;LL i,j;memset(prime, true, sizeof(prime));for(i=2; i<maxn; i++){if(prime[i]){p[k++]=i;for(j=i*i; j<maxn; j+=i)prime[j]=false;}}/*for(int i=0; i<10; i++)cout<<p[i]<<” “;*/}LL get(LL m, LL p){if(m<p)return 0;return m/p+get(m/p,p);}LL quickmod(LL a, LL b){LL ans = 1;while(b){if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans ;}int main(){isprime();int n;while(~scanf(“%d”,&n)){LL ans=1;LL m = quickmod(2,(LL)mod-2);for(int i=0; i<k&&p[i]<=n; i++){LL tmp = (get(n,p[i])*2+1)%mod;ans=ans*tmp%mod;}ans = ans*m%mod;ans = (ans+m%mod)%mod;printf(“%lld\n”,ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇hdu 1299 Diophantus of Alexandria下一篇Foj 1075 分解素因子
顶0踩0
何愁没有快乐的泉溪在歌唱，何愁没有快乐的鲜花绽放！
