首页 > 代码库 > HDU 4196

HDU 4196

2024-07-20 02:34:28   212人阅读

很容易由算术基本定理知道，完全平方数就是所有质因子指数为偶数的数。而求得N以下的质因子，可由前两篇的公式知，由N!与p的关系求得。对于指数为p的，用N!除去就可以，因为p必定属于N以内，且无重复。

至于除法，在下实在不会，学得别人的，记录一下。

MOD数除法，可以由费马小定理a^(p-1)=1 (mod p)其中p为素数，求得。因为X/Y即是X*(1/Y),为乘上逆元，所以由费马小定理知a^(p-2)即是逆元。用数乘上即可。

而对于p-2比较大的情况，只能用快速幂取模的方法求解了。

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const __int64 Maxp=10000010;const __int64 MOD=1000000007;bool isprime[Maxp];__int64 prime[Maxp],nprime;__int64 adds[Maxp];void Doprime(){	nprime=0;	memset(isprime,true,sizeof(isprime));	isprime[1]=false;	for(__int64 i=2;i<Maxp;i++){		if(isprime[i]){			prime[nprime++]=i;			for(__int64 j=i*i;j<Maxp;j+=i)			isprime[j]=false;		}	}}__int64 Pow(__int64 anst,__int64 poe){	__int64 ret=1;	__int64 tmp=anst;	while(poe){		if(poe&1) ret=(ret*tmp)%MOD;		tmp=(tmp*tmp)%MOD;		poe=(poe>>1);	}	return ret;}int main(){	__int64 anst;	Doprime();	adds[1]=1;	for(__int64 i=2;i<Maxp;i++)	adds[i]=(adds[i-1]*i)%MOD;	__int64 n;	while(scanf("%I64d",&n),n){		anst=1;		for(__int64	i=0;prime[i]<=n&&i<nprime;i++){			__int64 c=0;			for(__int64 t=prime[i];t<=n;t*=prime[i])			c+=(n/t);			if(c&1)			anst=(anst*prime[i])%MOD;		}		printf("%I64d\n",((adds[n]*Pow(anst,MOD-2))%MOD));	}	return 0;}

　　

HDU 4196


联系
我们