[51Nod 1035 最長(zhǎng)的循環(huán)節(jié)] 循環(huán)小數(shù)的性質(zhì)

知識(shí)點(diǎn)：數(shù)論 循環(huán)小數(shù)の性質(zhì) 歐拉公式

1. 題目鏈接##

[51Nod 1035 最長(zhǎng)的循環(huán)節(jié)]

2. 題意描述

正整數(shù)k的倒數(shù)1/k，寫(xiě)為10進(jìn)制的小數(shù)如果為無(wú)限循環(huán)小數(shù)，則存在一個(gè)循環(huán)節(jié)，求<=n的數(shù)中，倒數(shù)循環(huán)節(jié)長(zhǎng)度最長(zhǎng)的那個(gè)數(shù)，假如存在多個(gè)最優(yōu)的答案，輸出所有答案中最大的那個(gè)數(shù)。
1/6= 0.1(6) 循環(huán)節(jié)長(zhǎng)度為1
1/7= 0.(142857) 循環(huán)節(jié)長(zhǎng)度為6
1/9= 0.(1) 循環(huán)節(jié)長(zhǎng)度為1
(10≤n≤1000)

3. 解題思路

首先，需要介紹一下循環(huán)小數(shù)的幾個(gè)性質(zhì)。證明論文《康明昌-循環(huán)小數(shù)》

循環(huán)小數(shù)的每個(gè)循環(huán)節(jié)長(zhǎng)度為偶數(shù)，（記為2k），那么每個(gè)循環(huán)節(jié)中第i（1≤i≤k）個(gè)數(shù)字 + 第(i+k)個(gè)數(shù)字之和為9；

如果p是質(zhì)數(shù)，并且d是1p的循環(huán)節(jié)的位數(shù)，則d可以整除p?1；

如果1≤b<a， a沒(méi)有2或者5的質(zhì)因數(shù)，并且a與b互質(zhì)，那么ba的循環(huán)節(jié)位數(shù)等于：min{e∈N:10e≡1(moda)}；

如果1≤b<a， a沒(méi)有2或者5的質(zhì)因數(shù)，并且a與b互質(zhì)，那么ba的循環(huán)節(jié)位數(shù)必整除ψ(a)(即a的歐拉函數(shù));

如果n,m≥3, 2和5都不整除mn,并且n與m是互質(zhì)的正整數(shù)，則1mn的循環(huán)位數(shù)是1n與1m循環(huán)小數(shù)位數(shù)的最小公倍數(shù);

……，其他定理可以參考論文。

在這個(gè)題，我們需要用到的結(jié)論就是第3條。
需要特殊處理的是，分母含2或5的因數(shù)。如1235?？梢韵葘?span id="ze8trgl8bvbq" class="MathJax_Preview">2或5的因數(shù)提出來(lái)：

1235=15?47=247?110
1235的循環(huán)位數(shù)是跟 247是一樣多的。而 247循環(huán)位數(shù)也正是 147的循環(huán)位數(shù)。
數(shù)據(jù)比較小，所以暴力枚舉 e<script type="math/tex" id="MathJax-Element-218">e</script>即可。

4. 實(shí)現(xiàn)代碼

#include <bits/stdc++.h> using namespace std;typedef pair<int, int> PII;const int MAXN = 1000 + 5;int n;int q_pow(int a, int b, int mod) {int ret = 1;while(b > 0) {if(b & 1) ret = ret * a % mod;a = a * a % mod;b >>= 1;}return ret; }int calc(int x) {while((x & 1) == 0) x >>= 1;while(x % 5 == 0) x /= 5;if(x == 1) return 1;int e = 1;while(q_pow(10, e, x) != 1) e ++;return e; }PII ans[MAXN]; void init() {ans[1] = PII(1, 0);for(int i = 2; i < MAXN; i++) {int z = calc(i);if(ans[i - 1].second <= z) ans[i] = PII(i, z);else ans[i] = ans[i - 1];} }int main() { #ifdef ___LOCAL_WONZY___freopen("input.txt", "r", stdin); #endif // ___LOCAL_WONZY___init();while(~scanf("%d", &n)) {printf("%d\n", ans[n].first);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[51Nod 1035 最长的循环节] 循环小数的性质的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。