POJ 1091 跳蚤 扩展欧几里得+鸽巢原理

Description

Input

Output

Sample Input

2 4

Sample Output

12

Hint

Source

//400K	0MS
#include<stdio.h>
#define M 130007
long long num[M],s[M];
long long n,m,total,per;
void sum_factor()//分解质因子，存在num里面
{
    total=0;
    long long t=m;
    for(int i=2;i*i<=t;i++)
    {
        if(t%i==0)num[total++]=i;
        while(t%i==0)t/=i;
    }
    if(t!=1)num[total++]=t;
}
long long pow(long long x,long long y)//求x^y
{
    long long k=x;
    for(long long i=1;i<y;i++)
        x*=k;
    return x;
}
void dfs(long long a,long long b,long long c)//a在数组中的起始位置，b含的个数，c公共质因子的个数
{
    if(b==c)
    {
        long long t=m;
        //printf("(");
        for(long long i=0;i<c;i++)
        {
            //printf("%d ",s[i]);
            t/=s[i];//t表示每位上有几个包含质因子的数
        }
        //printf(")\n");
        per+=pow(t,n);//总共有多少个
    }
    else
    {
        for(long long i=a;i<total;i++)//递归回溯求解所有排列组合
        {
            s[b]=num[i];
            dfs(i+1,b+1,c);
        }
    }
}
int main()
{
    while(scanf("%I64d%I64d",&n,&m)!=EOF)
    {
        sum_factor();
        long long ans=pow(m,n);
        for(long long i=1;i<=total;i++)
        {
            per=0;
            dfs(0,0,i);
            if(i%2)ans-=per;//如果有奇数个公因数的n元组就相减
            else ans+=per;//如果有奇数个公因数的n元组就相加
        }
        printf("%I64d\n",ans);
    }
    return 0;
}