欧拉函数的概率解释:

1/p看做从1~n中某数有n的因子p的概率,则1-1/p是没有因子p的概率,最前面的n是指1~n的数的个数,由乘法公式可见F的意义

此题设函数F(n,m)为公因子为1的排列的个数,易见当m为质数时 

普遍看,总排列个数为,取p|m,则1/p为1~m的某数有因子p的概率,为前n个数都有p因子的概率,即这n+1个数有公因子p的概率

所以由乘法公式见:

恩,我理解的大概就是这个样子了...

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
typedef unsigned long long u64 ;
#define maxn 100010
u64 primet [ maxn ];
int pnum = 0 ;
void getprimtable()
{
    bool flag [ maxn ] = { false };
    for (long i = 2 ; i < maxn ; i ++)
    {
        if (! flag [ i ])
        {
            primet [ pnum ++] = i ;
            for (u64 j = i * i ; j < maxn ; j += i) flag [ j ] = true ;
        }
    }
}

bool isprime(u64 m)
{
    bool prime = 1;
    for (int i = 0; primet[i]*primet[i] <= m; i++)
    {
        if (m % primet[i] == 0)
        {
            prime = 0;
            break;
        }
    }
    return prime;
}

u64 pow64(u64 a, u64 b)
{
    u64 ans = 1, t = a;
    while (b)
    {
        if (b & 1)
        {
            ans *= t;
            b--;
        }
        t *= t;
        b >>= 1;
    }
    return ans;
}
u64 n, m;
int main()
{
    //freopen("in.txt", "r", stdin);
    getprimtable();
    u64 ans, t;
    while (cin >> n >> m)
    {
        ans = pow64(m, n);
        if (isprime(m))
            cout << ans - 1 << endl;
        else
        {
            for (u64 i = 0; primet[i]*primet[i] <= m; i++)
            {
                if (m % primet[i] == 0)
                {
                    while (m % primet[i] == 0) m /= primet[i];
                    t = pow64(primet[i], n);
                    ans = ans / t * (t - 1);
                }
            }
            if (m != 1)
            {
                t = pow64(m, n);
                ans = ans / t * (t - 1);
            }
            cout << ans << endl;
        }
    }
}