紫书例题 10-26 UVa 11440（欧拉函数+数论）

这里用到了一些数论知识

首先素因子都大于M等价与M！互质

然后又因为当k与M！互质且k>M!时当且仅当k mod M! 与M！互质（欧几里得算法的原理）

又因为N>=M, 所以N!为M!的倍数

所以只要求1到M！中与M！互质的数的个数,在乘上N!/M!

可以理解为每一块M！有这么多，然而N！中有很多块M！，所以乘上N!/M!

然后根据phifac[n] = phi[n!] = n!(1-1/p1)(1-1/p2)......(1-1/k)的定义可以得出

当n为质数的时候 phifac[n] = (n-1) * phifac[n-1]

当n不为质数的时候 phifac[n] = n * phifac[n-1]

（拿笔根据定义手算一下就可以得出）

边界是phifac[1] = phifac[2] = 1

书中问到为什么phifac[1] = 1

实际上是因为如果m=1，那么除1以外的所有数的素因子都大于1（素因子最小为2）

所以当m=1时后面乘的时候ans是为1的，如果ans为0的话最终答案为0

而实际上答案为N！-1

根据定义是phifac[1]=0，但根据这道题实际情况phifac[1]=1

最后注意中间结果可能溢出，所以用long long

#include<cstdio>

#include<vector>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 11234567;

const int MOD = 100000007;

bool is_prime[MAXN];

vector<int> prime;

int phifac[MAXN];

void init()

{

	memset(is_prime, true, sizeof(is_prime));

	is_prime[0] = is_prime[1] = false;

	REP(i, 2, MAXN)

	{

		if(is_prime[i]) prime.push_back(i);

		REP(j, 0, prime.size())

		{

			if(i * prime[j] > MAXN) break;

			is_prime[i*prime[j]] = false;

			if(i % prime[j] == 0) break;

		}

	}

}

int main()

{

	init();

	int n, m;

	phifac[1] = phifac[2] = 1;

	REP(i, 3, MAXN)

		phifac[i] = (long long)phifac[i-1] * (is_prime[i] ? i-1 : i) % MOD;

	while(~scanf("%d%d", &n, &m) && n)

	{

		int ans = phifac[m];

		REP(i, m + 1, n + 1) ans = (long long)ans * i % MOD;

		printf("%d\n", (ans - 1 + MOD) % MOD);

	}

	return 0;

}

巴特西

紫书例题 10-26 UVa 11440（欧拉函数+数论）

最新文章

热门文章

巴特西

紫书 例题 10-26 UVa 11440（欧拉函数+数论）

最新文章

热门文章

紫书例题 10-26 UVa 11440（欧拉函数+数论）