小红的循环节长度

C++(g++ 7.5.0) 解法, 执行用时: 21ms, 内存消耗: 400K, 提交时间: 2023-08-09 09:12:21

#include<bits/stdc++.h>
using namespace std;
long long phi(long long x){
    long long i;
    long long res=x;
    for(i=2;i*i<=x;i++){
        if(x%i==0){
            res=res/i*(i-1);
            while(x%i==0)x/=i;
        }
    }
    if(x>1)res=res/x*(x-1);
    return res;
}
long long power(__int128 a,long long b,long long p){
    __int128 res=1;
    while(b){
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
int main(){
    long long p,q,i,c2=0,c5=0;
    cin>>p>>q;
    q/=__gcd(p,q);
    while(q%2==0)q/=2,c2++;
    while(q%5==0)q/=5,c5++;
    if(q==1)return cout<<-1,0;
    long long temp=phi(q);
    long long mi=1e16;
    for(i=1;i*i<=temp;i++){
        if(temp%i==0){
            if(power(10,i,q)==1)mi=min(mi,i);
            if(power(10,temp/i,q)==1)mi=min(mi,temp/i);  
        }
    }
    cout<<max(c2,c5)<<' '<<mi;
}

C++(clang++ 11.0.1) 解法, 执行用时: 21ms, 内存消耗: 412K, 提交时间: 2023-08-07 19:27:13

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
int p,q;
int check(int x){
	int res=x;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			res=res/i*(i-1);
			while(x%i==0)x/=i;
		}
	}
	if(x>1)res=res/x*(x-1);
	return res;
}
int qim(__int128 a,int y,int z){
	__int128 res=1;
	while(y){
		if(y%2)res*=a;
		res%=z;
		a*=a;
		a%=z;
		y/=2;
	}
	return res%z;
}
signed main(){
	cin>>p>>q;
	int a=0,b=0;
	q/=__gcd(p,q);
	while(q%2==0)q/=2,a++;
	while(q%5==0)q/=5,b++;
	if(q==1){
		cout<<-1<<endl;
	}else{
		int tt=check(q);
		int minn=1e16;
		for(int i=1;i*i<=tt;i++){
			if(tt%i==0){
				if(qim(10,i,q)==1)minn=min(minn,i);
				if(qim(10,tt/i,q)==1)minn=min(minn,tt/i);
			}
		}
		cout<<max(a,b)<<" "<<minn<<endl;
	}
	return 0;
}

pypy3 解法, 执行用时: 98ms, 内存消耗: 24076K, 提交时间: 2023-08-08 11:52:10

import math
def phi(x: int) -> int:
    ans, i = x, 2
    while i * i <= x:
        if x % i == 0:
            ans = ans // i * (i - 1)
            while x % i == 0: x //= i 
        i += 1
    if x > 1: ans = ans // x * (x - 1)
    return ans
 
p, q = map(int, input().split())
g = math.gcd(p, q)
p //= g
q //= g # 化简
c2, c5 = 0, 0
while q % 2 == 0:
    q //= 2
    c2 += 1
while q % 5 == 0:
    q //= 5
    c5 += 1
if q == 1:
    print(-1)
    exit(0)
phiq = phi(q) # 拿到欧拉函数的值
ans, i = phiq, 2 # 找到最小的循环节
while i * i <= phiq:
    if phiq % i == 0: # 是因子
        if pow(10, i, q) == 1: ans = min(ans, i)
        if pow(10, phiq // i, q) == 1: ans = min(ans, phiq // i)
    i += 1
print(max(c2, c5), ans)

Python3 解法, 执行用时: 467ms, 内存消耗: 4656K, 提交时间: 2023-08-06 20:28:42

import math
p, q = map(int, input().split())
g = math.gcd(p, q)
p //= g
q //= g
c2 = 0
c5 = 0
while q % 2 == 0:
    q //= 2
    c2 += 1
while q % 5 == 0:
    q //= 5
    c5 += 1
if q == 1:
    print("-1")
    exit(0)

rq = q
mod = q
i = 2
while i*i <= q:
    if q % i == 0:
        rq //= i
        rq *= (i-1)
        while q % i == 0:
            q //= i
    i += 1
if q > 1:
    rq //= q
    rq *= (q-1)

ans = rq
i = 1
while i*i <= rq:
    if rq % i == 0:
        if pow(10, i, mod) == 1:
            ans = min(ans, i)
        if pow(10, rq//i, mod) == 1:
            ans = min(ans, rq//i)
    i += 1
print(max(c2, c5), ans)

详情