hdu -2837(指数循环节+欧拉函数)

àì夳堔傛蜴生んèń 2022-06-10 13:14 168阅读 0赞

**Problem Description**

**Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^f(n/10) for all n bigger than zero. Please calculate f(n)%m. (2 ≤ n , m ≤ 10^9, x^y means the y th power of x).**

**Input**

**The first line contains a single positive integer T. which is the number of test cases. T lines follows.Each case consists of one line containing two positive integers n and m.**

**Output**

**One integer indicating the value of f(n)%m.**

**Sample Input**

**2**

**24 20**

**25 20**

**Sample Output**

**16**

**5**

题目题意:题目就是让我们求f(n)%m,而函数f，是一个递归形式的函数,f(n)=(n%10)^(f(n/10)%m);

题目分析:分析到n,m比较大，而且又是指数形式，普通方法会炸。这里我们有一个重要的公式（数论的题目太多，太广了，得不停做，总结经验，积累公式）

A^x % m =A^ (x%phi\[m\]+phi\[m\]) %m (满足公式的条件x>=phi\[m\]) 其中phi\[m\]表示1到m之内，与m互质的对数（即欧拉函数的数值)

知道到了代码，在写代码的过程中，还是会有疑问的：

这是我写的时候遇到的疑问（比较Low，但是我的确当时不清楚）

1：很明显的一点是，公式既然有条件，那么我们在公式条件范围外（即x<phi\[m\],怎么办了），很明显只能去硬算，但是这个题目的表达式是f(n)=(n%10)^(f(n/10)%m),我们知道了f(n/10)是未知的，在不确定f(n/10)大小的情况下（就算我们可以递归求出来了，但是我们从当前层到下一层时，如果我们用了公式那么模数就是phi\[m\],没有就是m),是不同的，那么递归函数就很棘手。当时脑袋抽了，陷进出了，后来发现，我们的模数都可以变成phi\[m\],因为当x<phi\[m\]时，x%phi\[m\]不变，哈哈。所以我们递归的时候，把下一层的模数都变成phi\[m\]，只是在求fast\_pow的时候应当去判断一下，x与模数的大小关系，如果大，那么就的用公式，x%phi\[m\]+phi\[m\].取模还得加模。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #define ll long long
    using namespace std;
    
    ll get_euler(ll n)//求欧拉函数的数值
    {
        ll res=n,a=n;
        for (int i=2;i*i<=a;i++) {
            if (a%i==0) {
                res=res/i*(i-1);
                while (a%i==0) a=a/i;
            }
        }
        if (a>1) res=res/a*(a-1);
        return res;
    }
    ll fast_pow(ll base,ll k,ll mod)
    {
        ll ans=1;
        while (k) {
            if (k&1) {
                ans=ans*base;
                if (ans>mod)
                    ans=ans%mod+mod;
    
            }
            base=base*base;
           if (base>mod)
              base=base%mod+mod;
            k>>=1;
        }
        return ans;
    }
    
    ll f(ll n,ll m)//f函数的表达式
    {
        if (n<10) return n;
        ll phi=get_euler(m);//把下一层的模数都换成phi
        ll t=f(n/10,phi),ans;
        n=n%10;
        ans=fast_pow(n,t,m);//求当层的A^x
        return ans;
    
    }
    
    int main()
    {
        int t;
        scanf("%d",&t);
        while (t--) {
            ll n,m;
            scanf("%lld%lld",&n,&m);
            printf("%lld\n",f(n,m)%m);
        }
        return 0;
    }