首页 > 代码库 > bzoj 3031: 理科男
bzoj 3031: 理科男
Description
吃过草莓刨冰之后，Vani和cl有些疲倦地坐在一个长椅上。
“呐，玩得开心吗？”Vani忽然问道。
“嗯……很，很开心的说。”
“那么，我有一个问题想要问你呢。”
cl的脸有点红了起来。
“嗯……好吧。问、问吧……我会告诉你的哦……”
“那好。对于一个分数A / B……”
“嗯……哎？哎？！”
“……就是这个问题。我觉得这个问题好纠结啊……”
Vani淡定地说完这句话。
“啊？！哈啊？！”
对于给定的分数 A / B，求其在 K 进制下是有限小数还是循环小数。如果是有限小数，求小数点后的位数；如果是循环小数，则求混循环部分和循环节的长度又分别是多少。
注意，循环节指的是最短循环节，且混循环部分的长度也指最短。
Input
第一行一个正整数 T，表示测试数据的数目。
每个测试数据包含三个空格分隔的整数 A, B, K。含义如题目所示。
Output
对于每个测试数据，在单独的一行内输出两个空格分隔的整数 M, R。
其中 M 表示混循环部分的长度，R 表示循环节的长度。
如果 A / B 在 K 进制下是有限小数，则 R = 0，M 为小数点后面的位数；如果 A / B 在 K 进制下是纯循环小数，则 M = 0。
$minimize\space M,R\space s.t.$
$\frac{A}{B}=\frac{x}{(K^R-1)K^M}$
将$\frac{A}{B}$化为最简分数后，答案只和$B,K$有关若$gcd(B,K)>1$则有混循环部分，将$B$不断除以$gcd(B,K)$直到互质，除的次数即为$M$
R即为求$\frac{B}{gcd(B,K^M)}$在模K意义下与K互质的数构成的乘法群中的阶，答案是$\phi(K)$的约数，可以试除得到
#include<cstdio>typedef long long i64;i64 gcd(i64 a,i64 b){ for(i64 c;b;c=a,a=b,b=c%b); return a;}i64 phi(i64 x){ i64 y=x; for(int i=2;i64(i)*i<=x;++i)if(x%i==0){ y=y/i*(i-1); do x/=i;while(x%i==0); } if(x>1)y=y/x*(x-1); return y;}i64 mul(i64 a,i64 b,i64 p){ i64 c=0; for(;b;b>>=1,a=(a<<1)%p)if(b&1)c=(c+a)%p; return c;}i64 pw(i64 a,i64 n,i64 p){ i64 v=1; for(;n;n>>=1,a=mul(a,a,p))if(n&1)v=mul(v,a,p); return v;}i64 cal(i64 A,i64 B){ i64 x=phi(B),y=x; for(int i=2;i64(i)*i<=x;++i)if(x%i==0){ while(y%i==0&&pw(A,y/i,B)==1)y/=i; do x/=i;while(x%i==0); } if(x>1&&pw(A,y/x,B)==1)y/=x; return y;}int main(){ int T; for(scanf("%d",&T);T;--T){ i64 a,b,c; scanf("%lld%lld%lld",&a,&b,&c); i64 g=gcd(a,b); a/=g,b/=g; int a1=0; while(1){ i64 x=gcd(b,c); if(x==1)break; b/=x; ++a1; } printf("%d %lld\n",a1,b==1?0ll:cal(c,b)); } return 0;}
bzoj 3031: 理科男
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。