循环节

大家好，欢迎来到IT知识分享网。

循环节的定义

如果无限小数的小数点后，从某一位起向右进行到某一位止的一节数字循环出现，首尾衔接，称这种小数为循环小数，这一节数字称为循环节。

研究背景

给定一个整数$n$，求最小的$k$使$10^k\equiv 1$ ($mod$ $n$)。此时的$k$就等价于$\frac{1}{n}$的循环节的长度。
引理：对于$a^k\equiv 1$ ($mod$ $n$)，若$a$与$n$互质，那么最小的$k$必定是$\varphi (n)$的约数；若$a$与$n$有公因子，显然无解。
根据这个性质，只要枚举$\varphi (n)$的每个约数分别验证，就能求出循环节的最小长度$k$了。

例题：Big Integer

链接

2019牛客暑期多校训练营（第三场）D题

题意

给定$n,m,p$。$A(a,b)$表示一个由$a^b$个$1$组成的数。
求有多少对$(i,j)$，满足$1\le i\le n$，$1\le j\le m$，使得$A(i,j)\equiv 0(mod$ $p)$。
$(p,n,m\le 10^9)$

分析

11…111 = $\frac{10^n-1}{9}$ ≡ 0 (mod p)
等价于$10^n\equiv 1$ $(mod$ $9p)$
当$n̸=2,5$的倍数的时候，有$gcd(10,9p)=1$，因此$10^{\varphi (9p)}\equiv 1$ $(mod$ $9p)$
我们需要找到满足$10^i$ $mod$ $9p$的最小循环节长度$d$。
根据前面说到的性质，$d$必定是$\varphi (9p)$的约数，
暴力枚举$\varphi (9p)$的约数分别验证就能找到最小循环节$d$。
由于$d$的倍数都可能作为循环节，所以接下来我们要找到有多少对$(i,j)$，满足$d$ | $i^j$。
将$d$进行质因子分解，得到$d=p_1^{k1}{p}_2^{k2}...p_x^{kx}$，
考虑当$j$固定时，$i$必须是$g=p_1^{\lceil \frac{k1}{j}\rceil }{p}_2^{\lceil \frac{k2}{j}\rceil }...p_x^{\lceil \frac{kx}{j}\rceil }$的倍数。
因此一共有$\frac{n}{g}$个合法的$i$。
由于所有$k_i\le 30$，所以当$j\ge 30$时，$\lceil \frac{ki}{j}\rceil =1$，
因此只需计算从$1$到$30$的$j$的$g$值即可。
当$p=2,5$的倍数时，显然答案为$0$。

代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef double db; template<class T>inline void MAX(T &x,T y){ 
   if(y>x)x=y;} template<class T>inline void MIN(T &x,T y){ 
   if(y<x)x=y;} template<class T>inline void rd(T &x){ 
    x=0;char o,f=1; while(o=getchar(),o<48)if(o==45)f=-f; do x=(x<<3)+(x<<1)+(o^48); while(o=getchar(),o>47); x*=f; } const int M=1e5+5; int cas,cnt[M],mark[M]; ll n,m,p,prime[M]; ll Fast(ll a,ll b,ll P){ 
    ll res=0; while(b){ 
    if(b&1)res=(res+a)%P; a=(a+a)%P; b>>=1; } return res; } ll fast(ll a,ll b,ll P){ 
    ll res=1; while(b){ 
    if(b&1)res=Fast(res,a,P); a=Fast(a,a,P); b>>=1; } return res; } int main(){ 
    #ifndef ONLINE_JUDGE freopen("jiedai.in","r",stdin); // freopen("jiedai.out","w",stdout); #endif for(ll i=2;i<M;i++)if(!mark[i]) for(ll j=i*i;j<M;j+=i)mark[j]=1; rd(cas); while(cas--){ 
    rd(p),rd(n),rd(m); if(p%2==0||p%5==0){ 
   puts("0");continue;} ll P=9*p,phi=1,tmp=P; for(ll i=2;i*i<=P;i++){ 
    if(!mark[i]){ 
    int tp=1; while(tmp%i==0){ 
    tmp/=i; if(tp)phi*=i-1,tp=0; else phi*=i; } } } if(tmp>1)phi*=tmp-1; ll d=phi,res=0,ans=0; for(ll i=1;i*i<=phi;i++) if(phi%i==0&&fast(10,i,P)==1) { 
   MIN(d,i);break;} for(ll i=sqrt(phi);i;i--) if(phi%i==0&&fast(10,phi/i,P)==1) { 
   MIN(d,phi/i);break;} tmp=d; for(ll i=2;i*i<=d;i++)if(!mark[i]&&d%i==0){ 
    prime[++res]=i; cnt[res]=0; while(tmp%i==0)cnt[res]++,tmp/=i; } if(tmp>1)prime[++res]=tmp,cnt[res]=1; for(int j=1;j<=min(30ll,m);j++){ 
    tmp=1; for(int i=1;i<=res;i++) for(int t=1;t<=(cnt[i]+j-1)/j;t++) tmp*=prime[i]; ans+=n/tmp; if(j==30)ans+=(n/tmp)*(m-30); } printf("%lld\n",ans); } return (0-0); }