hdu 5407(LCM好题+逆元)

CRB and Candies

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 947 Accepted Submission(s): 442

Problem Description

CRB has

Input

There are multiple test cases. The first line of input contains an integer

Output

For each test case, output a single integer – LCM modulo 1000000007(

Sample Input

Sample Output

Author

KUT（DPRK）

这个题我是知道(n+1)*LCM(C(n,0),C(n,1)..C(n,n)) = LCM(1,2,3..n) 这个公式的，但是用错了方法求（1-n）的LCM。。（也就是经常用的那个lcm(a,b) = a/gcd(a,b)*b）但是这个公式里面是不允许取模的。。所以一直弄不出来。。然后在网上看到了很牛逼的公式。。数论真是很神奇啊。

我感觉这种题没接触过神牛也不一定能够解出来吧。。

还有一个人的题解提供了一种方法，不过没看懂，但是他提供了一种求解最小公倍数的方法。

---------------------------------------------------------------------------------------------------------------------------------------------------------------

http://www.cnblogs.com/crazyacking/p/4748294.html

分解质因数法：

先把这几个数分解质因数，再把它们一切公有的质因数和其中几个数公有的质因数以及每个数的独有的质因数全部连乘起来，所得的积就是它们的最小公倍数。

例如，求LCM[12，18，20，60]

因为12=（2）×[2]×[3]，18=（2）×[3]×3，20=（2）×[2]×{5}，60=（2）×[2]×[3]×{5}

其中四个数的公有的质因数为2（小括号中的数），

三个数的公有的质因数为2与3[中括号中的数]，

两个数的公有的质因数为5{大括号中的数}，

每个数独有的质因数为3。

所以，［12，18，20，60］=2×2×3×3×5=180。

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long LL;
const int N = 1000005;
const LL mod = 1000000007;
LL f[N];
LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}

LL extend_gcd(LL a,LL b,LL &x,LL &y){
    if(!b){
        x=1,y = 0;
        return a;
    }else{
        LL x1,y1;
        LL d = extend_gcd(b,a%b,x1,y1);
        x = y1;
        y = x1 - a/b*y1;
        return d;
    }
}
LL mod_reverse(LL a,LL n)
{
    LL x,y;
    LL d=extend_gcd(a,n,x,y);
    if(d==1) return (x%n+n)%n;
    else return -1;
}
int prime[N];
LL F[N];
bool only_divide(int n){
    int t = prime[n];
    while(n%t==0){
        n/=t;
    }
    if(n==1) return true;
    return false;
}
void init(){
    for(int i=1;i<N;i++){
        prime[i] = i;
    }
    for(int i=2;i<N;i++){  ///十分巧妙的一步,判断某个数是否只有唯一的质因子,只需要把每个数的倍数存下来
        if(prime[i]==i){
            for(int j=i+i;j<N;j+=i){
                prime[j] = i;
            }
        }
    }
    F[1] = 1;
    for(int i=2;i<N;i++){
        if(only_divide(i)){
            F[i] = F[i-1]*prime[i]%mod;
        }else F[i] = F[i-1];
    }
}
int main()
{
    init();
    int tcase;
    scanf("%d",&tcase);
    while(tcase--)
    {
        int n;
        scanf("%d",&n);
        LL inv = mod_reverse((n+1),mod);
        printf("%lld
",F[n+1]*inv%mod);
    }
    return 0;
}