HDU 4196

很容易由算术基本定理知道，完全平方数就是所有质因子指数为偶数的数。而求得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

最新文章

热门文章