QBXT 【可爱数字】

LMSH7 · 2018-06-14 19:27:40 · 个人记录

前方辣眼题解QAQ

利用一个玄学性质，幸运数s是k进制下的不具有循环节的最小的那个数（我这里表述不太准确，是那种数字排列相同，类似于环状的一组数中最小的的那一个），设一个f[i]数组表示k进制下i位数（由于可以有前导零嘛）的总选择（语言能力表达有限QAQ）数目 所以k^8-[k^4-(k^2-k)-k]-(k^2-k) 因为我们现在求的数的个数中n个为一组，就像环状，因为只有最小的那个可以，所以每个组只保留一个，所以总数除以n就是了

看着代码推倒推导一遍大致就能理解了，至于那个玄学性质。。。无力证明

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

long long const P=1000000007,M=100000;
int m;
long long n,k,g[M],f[M];

long long comp(long long b,long long c,long long m) //一个快速幂 
{
    long long ans=1;
    long long l=b;
    long long j=1;
    while (j<=c)
    {
        if ((j & c)>0) ans=(ans*l) % m;

        l=(l*l) % m; 

        c=c>>1;
    }
    return ans;
}

int main()
{
//  freopen("cute9.in","r",stdin);
//  freopen("cute9.out","w",stdout);
    cin>>n>>k;
    for (long long i=1;i*i<=n;i++)
        if (n % i==0)
        {
            g[++m]=i;//n的因子
            if (i*i<n) g[++m]=n/i;
        }

    sort(g+1,g+m+1);

    f[1]=k;

    for (int i=2;i<=m;i++)
    {
        f[i]=comp(k,g[i],P);

        cout<<f[i]<<endl;

        for (int j=1;j<=i-1;j++)
            if (g[i] % g[j]==0) f[i]=(f[i]+P-f[j]) % P;
    }
    printf("%lld\n",f[m]*comp(n,P-2,P) % P);
 } 

因为n的因子的循环串可以构成n位的循环串，就像8位中1，2，4都可反复循环得到8位，不符合玄学性质中要求没有循环这一条件。又因为每个因子中的可以构成这个因子的因子一定也是n的因子，所以就要将n的因子筛出来。