What is N? HDU - 4335

数论，欧拉函数降幂公式

题意

求 1 - M 中 n 中 n n ! = b ( <mtext>   </mtext> m o d <mtext>   </mtext> m ) 的个数

分析

欧拉函数降幂公式
A B ( m o d <mtext>   </mtext> m ) = A B <mtext>   </mtext> % <mtext>   </mtext> ψ ( m ) + ψ ( m ) ( B <= ψ ( m ) )

其中 ψ ( ) 是欧拉函数
1. n ! < ψ ( m ) 直接求 n n ! <mtext>   </mtext> % <mtext>   </mtext> m
2. n ! > ψ ( m ) 和 <mtext>   </mtext> n ! % ψ ( m ) ! = 0 暴力求解，已经可以利用降幂公式
3. n ! <mtext>   </mtext> % <mtext>   </mtext> ψ ( m ) = 0 这个时候就变成了 n 0 + ψ ( m ) ,指数固定，n变化，又因为 n = n + m ( m o d m ) ,所以从 n- n+m-1 是一个周期
同类题

参考代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef unsigned long long LL;//注意数据范围
LL Euler(LL n)//欧拉函数
{
    LL ans = n;
    for(LL i = 2; i * i <= n; ++i)
    {
        if(n % i == 0)
        {
            ans = ans / i *(i-1);
            while(n % i==0)
               n /= i;
        }
    }
    if(n != 1)
        ans = ans/n*(n-1);
    return ans;
}
LL qpow(LL q,LL a,LL m)//快速幂
{
    LL ans = 1;
    q %= m;
    while(a > 0)
    {
        if(a&1)
            ans = ans * q % m;
        q = q*q % m;
        a >>= 1;
    }
    return ans;
}
const int LEN = 1e5+200;
LL num[LEN];//记录一个周期
int main()
{
      LL t = 18446744073709551615;
           // 18446744073709551615
// cout<<(t)<<endl;
    int T;
    cin>>T;
    int kase = 0;

    while(T--)
    {
        LL ans = 0;
        LL b,p,M;
        cin>>b>>p>>M;
        if(p==1)
        {
            if(M==t)//防止溢出
                printf("Case #%d: 18446744073709551616\n",++kase,ans);
            else
                printf("Case #%d: %I64u\n",++kase,M+1);
            continue;
        }
        LL i = 0;
        LL cnt = 0;
        LL exp = 1;
        LL eu = Euler(p);
// LL pre = 1;
        for(;i <= M&& exp < eu; ++i)
        {
            if(qpow(i,exp,p)==b)
                ++ans;
            exp *= i+1;
        }
        for(; i <= M&&exp; ++i)
        {
            if(qpow(i,exp+eu,p)==b)
                ++ans;
            exp *= i+1;
            exp %= eu;
        }
        int j = 0;
        for(; i <= M&&j < p; ++i,++j)
        {
            if(qpow(i,eu,p)==b)
                ++ans,++cnt;
            num[j] = cnt;
        }
        if(i <= M)//i == M的时候未处理
        {
            LL tmp = M-i+1;//还有多少个未判断
             ans += tmp / p * cnt;//有多少个完整的循环周期
            tmp = tmp % p;
            if(tmp>0)
            ans += num[tmp-1];
        }
        printf("Case #%d: %I64u\n",++kase,ans);
    }


    return 0;
}