[NOIP模拟][容斥原理][快速幂]Heal

樣例輸入1：

2 3

樣例輸出1：

8

樣例輸入2：

8 8

樣例輸出2：

16711680

題目分析：

考場總結：對于這道題無話可說，有一種難度叫讀不懂題。考試時前面題花的時間比較多，然後面對這道長達2頁的題（以某種鬼畜的言情風格寫了一大堆廢話包裹題面），我愣是沒有讀懂，實際上這道題的題目要求轉化一下，就比較簡單（以前還做過一道這樣的題，那道題的題面沒有這麼複雜），比前面的兩道都還簡單·····是以啊，一道題不夠難，可以通過題面來增加其難度。

分析：是以這道題最後的意思就是求給定m，選取n個小于等于m的數（可以相同），使得這個n+1數整體互質及gcd為1，有多少種組合。那麼我們可以用整體減不互質的組合。整體是 mn （因為可以取相同的數）。而m是已知的，是以求出m的質因子，如果整體不互質，那麼gcd隻能是m的約數，是以容斥：減去gcd為一個質因子的個數的n次方，加上gcd為兩個質因子的乘積的個數的n次方，減去3個·········

附代碼：

#include<iostream>
#include<cstring>
#include<string>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cmath>
#include<iomanip>
#include<cctype>
#include<algorithm>
using namespace std;

const int mod=+;
const int N=;
int tot,num;
long long n,m,q[N],zhi[N],ans,p;

long long ksm(long long x,long long y)
{
    long long ret=;
    x%=mod;
    for(;y;y/=,x=(x*x)%mod)
        if(y&) ret=(ret*x)%mod;
    return ret;
}

void dfs(int cnt,int po,long long sum)//求一定個數質因子的乘積
{
    if(cnt==)
    {
        q[++tot]=sum;
        return;
    }
    for(int i=po;i<=num;i++)
        dfs(cnt-,i+,sum*zhi[i]);
}

void find(int x,int ci)//容斥
{
    if(x==) return;
    tot=;
    dfs(num-x+,,);
    for(int i=;i<=tot-cnt+;i++)
        ans=(ans+mod+ksm(m/q[i],n)*ci)%mod;
    find(x-,ci*(-));
}

int main()
{
    //freopen("heal.in","r",stdin);
    //freopen("heal.out","w",stdout);

    scanf("%I64d%I64d",&n,&m);
    p=m;
    for(long long i=;i*i<=p;i++)//求m的質因子
    {
        if(p%i==)
        {
            zhi[++num]=i;
            while(p%i==)
            {
                p/=i;
            }
        }
    }   
    if(p>) zhi[++num]=p;
    ans=ksm(m,n);
    find(num,-);
    printf("%I64d",ans);

    return ;
}