POJ 1091ノミ因子分解+反発原理

タイトルリンク:http://poj.org/problem?id=1091
解析:カード上の符号がそれぞれa 1,a 2,...,an,M,ノミジャンプ対応符号のカードの回数がそれぞれx 1,x 2,...,xn,xn+1であると仮定すると,既知の条件を満たすには方程式a 1*x 1+a 2*x 2+...+an*xn+M*xn+1=1の解,すなわちgcd(a 1,a 2,...,an,m)=1を満たすだけで,次にMを質量因子分解し,共通因子が1でない場合を排除すればよい.公因子数が1〜num内のすべての条件に合致する配列(a 1,a 2,...,an)の数をそれぞれ探し出し,反発原理で解決できた.
実装コードは次のとおりです.

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
const int N=64;
int prime[N],num;
void divide(int m)
{//     
    num=0;
    for(int i=2;i*i<=m;i++)
    {
        if(m%i==0)
        {
            prime[++num]=i;
            m/=i;
            while(m%i==0) m/=i;
        }
    }
    if(m>1) prime[++num]=m;
}
LL quick_mul(LL a,LL b)
{//  a^b
    LL ans=1;
    while(b)
    {
        if(b&1) ans*=a;
        a*=a;
        b>>=1;
    }
    return ans;
}
LL temp,ans;
int p[N],m,n;
void dfs(int b,int cnt,int c)
{//    c          
 //b          ,cnt           
    if(cnt==c)
    {
        int x=m;
        for(int i=1;i<=c;i++)
          x/=p[i];
        temp+=quick_mul(x,n);
        return ;
    }
    for(int i=b+1;i<=num;i++)
    {
        p[cnt+1]=prime[i];
        dfs(i,cnt+1,c);
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=-1)
    {
        ans=0;
        divide(m);
        for(int i=1;i<=num;i++)
        {
            temp=0;
            dfs(0,0,i);
            if(i&1) ans+=temp;
            else ans-=temp;
        }
        ans=quick_mul(m,n)-ans;
        printf("%lld
",ans);
    }
    return 0;
}