JZOJ3384

JZOJ3384

Description&Data Constraint

吃过草莓刨冰之后，Vani和cl有些疲倦地坐在一个长椅上。

“呐，玩得开心吗？”Vani忽然问道。

“嗯……很，很开心的说。”

“那么，我有一个问题想要问你呢。”

cl的脸有点红了起来。

“嗯……好吧。问、问吧……我会告诉你的哦……”

“那好。对于一个分数A / B……”

“嗯……哎？哎？！”

“……就是这个问题。我觉得这个问题好纠结啊……”

Vani淡定地说完这句话。

“啊？！哈啊？！”

对于给定的分数 A / B，求其在 K 进制下是有限小数还是循环小数。如果是有限小数，求小数点后的位数；如果是循环小数，则求混循环部分和循环节的长度又分别是多少。

注意，循环节指的是最短循环节，且混循环部分的长度也指最短。

Solution

意味深长的开头

回到题目，题意很简洁，就是求一个分数 A B dfrac{A}{B} BA​ 在 K K K 进制下的循环节位数和循环节前（即混循环部分）的位数。

先把 A B dfrac{A}{B} BA​ 约成既约分数，那么这时候的 A A A 已经没用了，就不用管。那么现在来想一下有关 B B B 和 K K K 的性质。

首先证明一下当 gcd ⁡ ( B , K ) = 1 gcd(B,K)=1 gcd(B,K)=1 时，混循环的位数是0。

设 a 1 = A , a i = K × a i − 1 m o d B , K × K ′ ≡ 1 ( m o d B ) a_1=A,a_i=Ktimes a_{i-1} mod B,Ktimes K'equiv 1pmod{B} a1​=A,ai​=K×ai−1​modB,K×K′≡1(modB) （即 K ′ K' K′是 K K K在 m o d B mod B modB 意义下的逆元）。

假设最早出现重复的位置 a p = a q ( p < q ) a_p=a_q(p<q) ap​=aq​(p<q)。

如果 p ≠ 1 pnot=1 p​=1，那么 a p − 1 = a p K m o d B = a p × K ′ m o d B = a q × K ′ m o d B = a q − 1 a_{p-1}=dfrac{a_p}{K}mod B=a_ptimes K' mod B=a_qtimes K' mod B=a_{q-1} ap−1​=Kap​​modB=ap​×K′modB=aq​×K′modB=aq−1​ 。

显然出现了更早的重复，与题设矛盾，所以就有 p = 1 p=1 p=1 。

所以原分数是个纯循环分数。

那么当 gcd ⁡ ( B , K ) ≠ 1 gcd(B,K)not=1 gcd(B,K)​=1的时候，考虑怎么求出混循环部分长度。

有种方法就是记录下 A × K m o d B Atimes K mod B A×KmodB 的值（ A K AK AK），然后每次令 B B B 去除 gcd ⁡ ( B , A K ) gcd(B,AK) gcd(B,AK)，直到 gcd ⁡ ( B , K ) = 1 gcd(B,K)=1 gcd(B,K)=1，除的次数就是答案。这里我不是很懂，大家可以自己想一下。

那么当除到 gcd ⁡ ( B , K ) = 1 gcd(B,K)=1 gcd(B,K)=1的时候，如果 B = 1 B=1 B=1，说明这是个令人愉快的有限小数！循环节长度输出0即可。

那如果 B ≠ 1 Bnot=1 B​=1，设循环节长度为 x x x，就有 a x = a 1 × K x m o d B = a 1 a_x=a_1times K^xmod B=a_1 ax​=a1​×KxmodB=a1​，所以 K x m o d B = 1 K^xmod B=1 KxmodB=1，这就是一个经典的求 K K K 模 B B B 的阶问题。

由欧拉定理可知 K φ ( B ) ≡ 1 ( m o d B ) K^{varphi(B)}equiv1pmod{B} Kφ(B)≡1(modB)，由阶的性质可得 x ∣ φ ( B ) x|varphi(B) x∣φ(B)。

我们可以将 φ ( B ) varphi(B) φ(B) 分解质因数，同时令答案 a n s = φ ( B ) ans=varphi(B) ans=φ(B)。

考虑对于 φ ( B ) varphi(B) φ(B) 的每个质因数 p p p，如果 K x p ≡ 1 ( m o d B ) K^{frac{x}{p}}equiv1pmod{B} Kpx​≡1(modB)，就令 x = x p x=frac{x}{p} x=px​，否则转下一个质因数。

最后的 x x x 就是答案。

Code

#include<cmath>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int t,tot;
ll n,m,k,x,a,g,ans,phi,p[1000005];
ll gcd(ll x,ll y)
{ll r=x%y;while (r) x=y,y=r,r=x%y;return y;
}
ll mul(ll x,ll y,ll mod)
{ll res=0;while (y){if (y&1) res=(res+x)%mod;x=(x+x)%mod;y>>=1;}return res;
}
ll ksm(ll x,ll y,ll mod)
{ll res=1;while (y){if (y&1) res=mul(res,x,mod);x=mul(x,x,mod);y>>=1;}return res;
}
int main()
{freopen("T1.in","r",stdin);scanf("%d",&t);while (t--){scanf("%lld%lld%lld",&n,&m,&k);tot=0;g=gcd(n,m);n/=g;m/=g;a=mul(k,n,m);ans=0;while (true){g=gcd(m,k);if (g==1) break;m/=gcd(m,a);++ans;}printf("%lld ",ans);if (m==1){printf("0n");continue;}x=phi=m;for (int i=2;x>1&&i<=sqrt(m);++i){if (x%i==0){phi=phi/i*(i-1);while (x%i==0) x/=i;}}if (x>1) phi=phi/x*(x-1);x=phi;for (int i=2;x>1&&i<=sqrt(phi);++i){if (x%i==0){p[++tot]=i;while (x%i==0) x/=i;}}if (x>1) p[++tot]=x;for (int i=1;i<=tot;++i)while(ksm(k,phi/p[i],m)==1&&phi%p[i]==0) phi/=p[i];printf("%lldn",phi);}return 0;
}