有限小数

题目描述

现在有一个正整数n,可以证明存在若干个正整数d使得1/n在d进制下为有限小数，输出最小的d。

输入

单组输入第一行一个正整数$n(2\le n\le 10^{12})$

输出

一个正整数d

样例

输入	输出
9	3
999	111

AC代码

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

int main(){
    long long n;
    cin>>n;
    long long ans=1;
    long long tmp=n;

    //求n的质因数的乘积
    for(long long i=2;i*i<=tmp;i++){
        if(tmp%i==0){
            ans*=i;
            while(tmp%i==0){
                tmp/=i;
            }
        }
    }
    if(tmp>1) ans*=tmp;
    
    

    cout<<ans<<endl;
    return 0;
}

正确性证明

若$1/n$可以在d进制表达为有限小数，那么一定有：

\[\frac{1}{n}=\frac{a_1}{d}+\frac{a_2}{d^2}+\dots+\frac{a_m}{d^m} \]

其中$a_i< d(1\le i\le m)$，且$a$为正整数，$m$是一个正整数。将两边同乘$nd^m$得：

$$ d^m=n(a_1d^{m-1}+\dots+a_md^0)

\[ 故只要$d^m$是n的倍数，$1/n$在d进制下就为有限小数。将n进行质因数分解，由唯一分解定理知只能分解为一种形式，设d为n的质因数的乘积，易知此时总存在m使得n|$d^m$，并且显然，这个d是最小的。 \]