jzoj 5348. 【NOIP2017提高A组模拟9.5】心灵治愈

Description

Input

Output

Solution

---

Explanation

题目真把我看吐了，又臭又长的题面完全没有阅读的欲望好吧
其实就是有(n+1)个数，已知第n+1个数是m，然后第1~n个数∈[1,m]，求这些数互质的方案数
正难则反
容易得出总方案是(m^{n})的
我们再减去重复的就好了
将m分解质因数，再用容斥减就好了

Code

#include <cstdio>
#include <algorithm>
#include <cmath>
#define MO 1000000007
#define ll long long
#define open(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
int tot,i,prime[30000];
ll n,m,t,ans;
ll ksm(ll x,ll y)
{
    ll sum=1;x%=MO;
    while (y)
    {
        if (y&1) sum=(sum*x)%MO;
        x=(x*x)%MO;
        y>>=1;
    }
    return sum;
}
void dg(int x,ll y,int z)
{
    if (x>tot)
    {
        ans=(ans+ksm(m/y,n)*(z%2==0?1:-1)+MO)%MO;
        return;
    }
    dg(x+1,y*prime[x],z+1);
    dg(x+1,y,z);
}
int main()
{
    open("heal");
    scanf("%lld%lld",&n,&m);
    t=m;
    for (i=2;i<=floor(sqrt(m));i++)
    {
        if (t%i==0)
        {
            prime[++tot]=i;
            while (t%i==0) t/=i;
        }
    }
    if (t>1) prime[++tot]=t;
    dg(1,1,0);
    printf("%lld",ans);
    return 0;
}