链接:

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2435

题意:

给定正整数N和M,统计2和N!之间有多少个整数x满足:x的所有素因子都大于M(2≤N≤1e7,1≤M≤N,N-M≤1e5)。
输出答案除以100000007的余数。例如,N=100,M=10时答案为43274465。

分析:

因为M≤N,所以N!是M!的整数倍。“所有素因子都大于M”等价于和M!互素。
另外,根据最大公约数的性质,对于k>M!,k与M!互素当且仅当k mod M!与M!互素。
这样,只需要求出“不超过M!且与M!互素的正整数个数”,再乘以N!/M!即可。
这样,问题的关键就是求出phi(M!)。因为有多组数据,考虑用递推的方法求出所有的phifac(n)=phi(n!)。
由phi函数的公式:phi(n) = n(1-1/p1)(1-1/p2)...(1-1/pk),
如果n不是素数,那么n!和(n-1)!的素因子集合完全相同,因此phifac(n)=phifac(n-1)*n;
如果n是素数,那么还会多一项(1-1/n),即(n-1)/n,约分得phifac(n)=phifac(n-1)*(n-1)。

代码:

 import java.io.*;
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*; public class Main {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
final long MOD = (long)1e8 + 7;
final int UP = (int)1e7 + 5;
boolean isp[] = new boolean[UP];
long phifac[] = new long[UP]; void constant() {
fill(isp, true);
int u = (int)sqrt(UP+0.5);
for(int i = 2; i <= u; i++) if(isp[i]) {
for(int j = i*i; j < UP; j += i) isp[j] = false;
}
phifac[1] = phifac[2] = 1;
for(int i = 3; i < UP; i++)
phifac[i] = phifac[i-1] * (isp[i] ? i-1 : i) % MOD;
} void MAIN() {
constant();
while(true) {
int n = cin.nextInt();
int m = cin.nextInt();
if(n + m == 0) break;
long ans = phifac[m];
for(int i = m+1; i <= n; i++) ans = ans * i % MOD;
System.out.println((ans-1+MOD)%MOD); // 注意这里要减1,因为题目从2开始统计
}
} public static void main(String args[]) { new Main().MAIN(); }
}
05-11 15:51