【HDOJ 5407】 CRB and Candies (大犇推导

【HDOJ 5407】 CRB and Candies (大犇推导

【HDOJ 5407】 CRB and Candies

赛后看这题题解仅仅有满眼的迷茫………………

g(N) = LCM(C(N,0),C(N,1),...,C(N,N))

 f(n) = LCM(1, 2, ..., n)f(n) = LCM(1,2,...,n), the fact g(n) = f(n+1) / (n+1)g(n) = f(n+1)/(n+1)

f(n) = LCM(1, 2, ..., n)f(1) = 1

If n =p^{k}n =p​k​​ then f(n) = f(n-1) times pf(n) = f(n−1)× p, else f(n) = f(n-1)f(n) = f(n−1).

和不断的woc…… 后来QAQ巨找到了推导的文章。

。。

恩……贴上来……

感觉我有公式恐惧症。。

。

看到长串公式就犯晕= = 巨巨们研究研究吧…………

感觉依据题解能做出来已经非常好了

事实上这题另一点是要取余 因为须要取余 不能做除法 因此要求个分母的乘法逆元 刚好在攻数论的扩欧，扩欧小费马都能做 前一篇有扩欧的不错的帖子链接 有兴趣的能够去瞅瞅

本题代码例如以下:

#include <iostream>
#include <cstdio>
#include <cstring>using namespace std;
#define sz 1000000
#define ll long long
const int mod = 1e9+7;int p[sz+1];
ll f[sz+1];bool ok(ll x)
{int t = p[x];while(x%t == 0 && x > 1) x /= t;return x == 1;
}void Init()
{int i,j;for(i = 1; i <= sz; ++i) p[i] = i;for(i = 2; i <= sz; ++i)if(p[i] == i)for(j = i+i; j <= sz; j += i)if(p[j] == j) p[j] = i;f[0] = 1;for(i = 1; i <= sz; ++i){if(ok(i)) f[i] = f[i-1]*p[i]%mod;else f[i] = f[i-1];}
}
//扩欧
//int e_gcd(int a,int b,int &x,int &y)
//{
//    if(!b)
//    {
//        x = 1;
//        y = 0;
//        return a;
//    }
//    ll tmp = x,ans = e_gcd(b,a%b,x,y);
//    tmp = x;
//    x = y;
//    y = tmp - a/b*y;
//    return ans;
//}ll pow(ll a,int m)
{ll ans = 1;for(;m; m >>= 1, a= a*a%mod)if(m&1) ans = ans*a%mod;return ans;
}ll cal(int a,int m)
{
//扩欧
//    int x,y;
//    int gcd = e_gcd(a,m,x,y);
//    return (x/gcd+m)%m;
//小费马return pow(a,m-2);
}int main()
{Init();int t,n;scanf("%d",&t);while(t--){scanf("%d",&n);printf("%lldn",f[n+1]*cal(n+1,mod)%mod);}return 0;
}

转载于:.html