1/n循环节长度

/*

 *  求1/i的循环节长度的最大值，i<=n

 */

const int MAXN = ;

int res[MAXN];  //  循环节长度

int main()

{

    memset(res, , sizeof(res));

    int i, temp, j, n;

    for (temp = ; temp <= ; temp++)

    {

        i = temp;

        while (i %  == )

        {

            i /= ;

        }

        while (i %  == )

        {

            i /= ;

        }

        n = ;

        for (j = ; j <= i; j++)

        {

            n *= ;

            n %= i;

            if (n == )

            {

                res[temp] = j;

                break;

            }

        }

    }

    int max_re;

    while (cin >> n)

    {

        max_re = ;

        for (i = ; i <= n; i++)

        {

            if (res[i] > res[max_re])

            {

                max_re = i;

            }

        }

        cout << max_re << endl;

    }

    return ;

}

原文：链接1

原文：链接2

简单来说就是，一个整数的倒数的循环节，就是求10x≡1(mod n)10x≡1(mod n)，很明显，如果gcd(10,n)≠1gcd(10,n)≠1的话，就无解。如果存在解的话，根据欧拉公式，那么这个解 x|phi(n)x|phi(n)，所以直接暴力枚举xx就好了。

#include <bits/stdc++.h>

using namespace std;

int phi(int m) {

    int ans = m;

    for(int i=; i*i<=m; i++) {

        if(m%i==) {

            ans = ans / i * (i - );

            while(m%i==) m /= i;

        }

    }

    if(m>) ans = ans / m * (m - );

    return ans;

}

int fp(int a, int n, int p) {

    int r = ;

    while(n) {

        if(n&) r = r * a % p;

        a = a * a % p;

        n >>= ;

    }

    return r;

}

int main() {

    int n;

    cin >> n;

    int ans = , cnt = ;

    for(int p=; p<=n; p++) if(__gcd(, p) == ) {

        int phn = phi(p);

        for(int i=; i<=phn; i++) {

            if(phn%i ==  && fp(, i, p) == ) {

                if(i>cnt) {

                    cnt = i;

                    ans = p;

                }

                break;

            }

        }

    }

    cout << ans << endl;

    return ;

}