POJ 1091 跳蚤（质因数分解+容斥原理+思维）

这个题挺考验思维的

这个题目需要转化一下题意，假设有 n 张卡片

由于向左向右并没有什么区别，所以题目可以转化为： a[1]*x[1]+a[2]*x[2]+……a[n]*x[n]+m*x[n+1]=1

那么需要 gcd(a[1],a[2],……a[n],m) =1 才能满足题意，……(可能很多大佬一眼就能看出来，但是还是证明一下吧)

• 证：当 gcd(a[1],a[2],……a[n],m) != 1 时，
• 方程两边可以同时除以 gcd,即方程变为：
• a[1]/gcd*x[1]+a[2]/gcd*x[2]+……+a[n]/gcd*x[n]+m/gcd*x[n+1] = 1/gcd
• 由于 数组 a[]，数组 x[] 都要求是整数，而 1/gcd 必不可能是整数，所以 gcd = 1，一定成立
• 证毕

这个问题到这里已经解决一半了 ，数组 a[] 全部小于 m，且允许重复 ，那么 数组 a[] 的每一个位置都可以安放 [1,m] 区间内所有的数，这是所有方案数

从这里面减去 gcd!=1 的情况，入手点从 m 下手

如果选取 m 的某一因数 x , 那么只要数组 a[] 中全部包含 x 这个因数即可

答案为   ,  (我们知道在 [1,m]范围内，包含因数 x 的个数有  个，每个位置都有这  种选择)

    ll n,m,t;
    //int a[N];
    vector<int> prime;

ll pow_mod(ll a,ll x)
{
    ll ans=1;
    while(x){
        if(x&1) ans=ans*a;
        x>>=1;
        a=a*a;
    }
    return ans;
}

void get_factor(int n)
{
    prime.clear();
    for(int i=2;i*i<=n;i++){
        if(n%i) continue;
        while(n%i==0) n=n/i;
        prime.pb(i);
    }
    if(n>1) prime.pb(n);
}

int main()
{
    IOS;
    while(cin>>n>>m){
        get_factor(m);
        ll ans=pow_mod(m,n);
        int up=1<<prime.size();
        for(int i=1;i<=up-1;i++){
            int bits=0,pos=0,cur=i;
            ll lcm=1;
            while(cur){
                if(cur&1) lcm=lcm*prime[pos],bits^=1;
                cur>>=1,pos++;
            }
            if(bits) ans-=pow_mod(m/lcm,n);
            else ans+=pow_mod(m/lcm,n);
        }
        cout<<ans<<endl;
    }
    //PAUSE;
    return 0;
}