又是一道不明觉厉的题,做这道题需要分析以下几个点:
1.如果k的任意素因子大于M,那么说明k和M!一定互质。
原因:任何数都可以写成一个唯一分解式子:k = p1^a1 * p2^a2 * ……;(p1 < p2 < p3……且都是质数)。
那么如果k的任意素因子大于M,那么说明 p1 > M, 又因为 M! = 1 * 2 * …… * M;所以k和M!一定没有除了1以外约束。
2.欧拉公式:小于一个数(n)的所有质因子 = n * (1 - 1/p1)(1- 1/p2) ……(1-1/pk)。
3.如何N和M互质,那么N % M 与 M 互素。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> #include<stack> #include<queue> #include<map> #include<set> #include<list> #include<cmath> #include<string> #include<sstream> #include<ctime> using namespace std; #define _PI acos(-1.0) #define INF (1 << 10) #define esp 1e-9 #define MOD 100000007 typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> pill; /*=========================================== ===========================================*/ #define MAXD 10000000 + 1 int is_Prime[MAXD]; LL phi[MAXD]; /* 小于i!的素因子个数*/ void Get_Prime(){ /*筛选法打素数表*/ memset(is_Prime,0,sizeof(is_Prime)); /*1代表不是素数,0代表是素数*/ is_Prime[1] = 0; for(int i = 2 ; i <= sqrt(MAXD) ; i++)if(!is_Prime[i]){ for(int j = i * i ; j < MAXD ; j += i) is_Prime[j] = 1; } } void init(){ Get_Prime(); /*打出1 ~ 1000000的素数表*/ phi[1] = 1; phi[2] = 1; for(int i = 3 ; i < MAXD ; i++) phi[i] = (LL)(is_Prime[i] == 1 ? i * phi[i - 1] : (i - 1) * phi[i - 1]) % MOD; } int main(){ init(); /*预处理*/ int N,M; while(scanf("%d%d",&N,&M)){ if(!N && !M) break; LL ans = phi[M]; for(int i = M + 1 ; i <= N ; i++) ans = ans * i % MOD; printf("%lld\n",(ans - 1 + MOD) % MOD); } return 0; }
【UVA】11440 - Help Tomisu,布布扣,bubuko.com
原文:http://blog.csdn.net/u013451221/article/details/38587495