【题解】牛牛的小幂幂

题意

给你一个十进制下的数a，问你在k进制下，a的最小多少次幂个位数是1，次幂要大于0，若无解输出-1

题解

解法一

题意转化一下就会变成求解中最小的n是多少，无解输出-1，首先易知若则无解，那么我们考虑a和k互质的情况，根据欧拉定理，若有a和k互质则,这说明a的次幂模k余1的循环节至少是，但题目要求的是最小次幂，那么一定是最小的吗，不一定。根据同余式的性质那么两边的任意次幂也是同余的。也就是说可以拆成其中，即为的因子，所以的因子可能是更小的解，我们可以求出的因子然后对他的因子进行检验从而获得最小的解。时间复杂度为。

解法二

使用EXBSGS来暴力求解最小值，需要较小的常数才能过。

代码

int phi(int n)
{
    int res=n;
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0)
        {
            res=res-res/i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
    {
        res=res-res/n;
    }
    return res;
}
long long quickmod(long long a,long long b,long long mod)
{
    long long ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b=b/2;
    }
    return ans;
}
class Solution {
public:
    /**
     * 
     * @param t int整型 t组
     * @param a int整型vector 
     * @param k int整型vector 
     * @return int整型vector
     */
    vector<int> solve(int t, vector<int>& a, vector<int>& k) {
        // write code here
        vector<int>s;
        for(int _=0;_<t;_++)
        {
            if(__gcd(a[_],k[_])!=1)
        {
            s.push_back(-1);
            continue;
        }
        int n=phi(k[_]);
        int ans=n;
        for(int i=1; i*i<=n; i++)
        {
            if(n%i==0)
            {
                if(quickmod(a[_],i,k[_])==1)
                    ans=min(ans,i);
                if(quickmod(a[_],n/i,k[_])==1)
                    ans=min(ans,n/i);
            }
        }
        s.push_back(ans);
        }
        return s;
    }
};

EXBSGS

#include <unordered_map>
unordered_map <int,int> Hash;
#define mul(a,b,p) (1ll*(a)*(b)%p)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int exBSGS(int a,int b,int p)
{
    a%=p,b%=p;
    if(!b&&!a) return 1;
    if(!a) return -1;
    if(!b)
    {
        int ret=0,d;
        while((d=gcd(a,p))!=1)
        {
            ++ret,p/=d;
            if(p==1) return ret;
        }
        return -1;
    }
    int ret=0,A=a,B=b,P=p,C=1,d;
    while((d=gcd(A,P))!=1)
    {
        if(B%d) return -1;
        P/=d,B/=d;
        C=mul(C,A/d,P);
        ++ret;
        if(C==B) return ret;
    }
    Hash.clear();
    int f=1,t=sqrt(P)+1;
    for(int i=0;i<t;i++)
    {
        Hash[mul(f,B,P)]=i;
        f=mul(f,A,P);
    }
    int tf=f;
    f=mul(f,C,P);
    for(int i=1;i<=t;i++)
    {
        if(Hash.find(f)!=Hash.end()) return ret+i*t-Hash[f];
        f=mul(f,tf,P);
    }
    return -1;
}
class Solution {
public:
    /**
     * 
     * @param t int整型 t组
     * @param a int整型vector 
     * @param k int整型vector 
     * @return int整型vector
     */
    vector<int> solve(int t, vector<int>& a, vector<int>& k) {
        // write code here
        vector<int>s;
        for(int i=0;i<t;i++)
        {
            int ans=exBSGS(a[i],1,k[i]);
            s.push_back(ans);
        }
        return s;
    }
};