本题主要是计算的1 / x小数的循环节的长度是多少
分数化小数其实也挺简单的
对于一个分母为x的分数
那么他的小数循环节长度最多为x- 1
这也是我打表得出的规律
所以数组的大小需要注意了
这个题中x < 1000
那么开两个1000的数组就OK了。
直接算的程序如下
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <ctime>
#define MAXN 111111
#define INF 100000007
using namespace std;
int rm[1011], qt[1011];
int gao(int m, int n)
{memset(rm, 0, sizeof(rm)); //rm用来存余数的位置memset(qt, 0, sizeof(qt)); //qt存的是各位小数m = m % n;for(int i = 1; i <= 1000; i++) // 分母最大为1000则最多有1000位。{rm[m] = i;m *= 10;qt[i] = m / n;m = m % n;if(m == 0) return 0;if(rm[m] != 0) /*若该余数对应的位在前面已经出现过*/return i - rm[m] + 1;}
}
int main()
{int ans = -1, pos;for(int i = 2; i < 1000; i++){int tmp = gao(1, i);if(tmp > ans)ans = tmp, pos = i;}cout << pos << endl;return 0;
}
利用这个程序我们还能得到一个分数 m / n化成小数的程序,循环节部分用括号包围
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <ctime>
#define MAXN 111111
#define INF 100000007
using namespace std;
int rm[1011], qt[1011];
int main()
{int m, n, i, j;scanf("%d%d", &m, &n);printf("%d.", m / n);m = m % n;for(i = 1; i <= 1000; i++){rm[m] = i;m *= 10;qt[i] = m / n;m = m % n;if(m == 0){for(j = 1; j <= i; j++) printf("%d", qt[j]);break; /*退出循环*/}if(rm[m] != 0) /*若该余数对应的位在前面已经出现过*/{for(j = 1; j <= i; j++){if(j == rm[m]) printf("[");printf("%d", qt[j]);}printf("]");break;}}return 0;
}
但是对本题的话，直接算的复杂度还是n^2的。
这里还有一个重要的结论
对于一个形如 1 / x的分数
找出最小的999...99使得x能整除999....999 那么 这个999....9有多少位，
这个分数转化为小数循环部分就有多少位。
不过前提是要把2和5因子都除掉。
因为形如999...99是永远没法被5和2整除的。
那么为什么这样就对呢？
我们都知道0.（9）这个循环小数跟1是等价的
所以我们的目标就是让1 /x转化后的小数乘以x然后== 0.(9)
然后实际上就是一堆9凑成的数能被x整除就找到循环节了。
那么用这个我们又得到一种方法。 不过好像还是最坏n^ 2的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <ctime>
#define MAXN 111111
#define INF 100000007
using namespace std;
int gao(int x)
{int now = 0;int step = 0;while(x % 2 == 0) x /= 2;while(x % 5 == 0) x /= 5;if(x == 1) return 0;while(1){now = (now * 10 + 9) % x;step++;if(now == 0) break;}return step;
}
int main()
{for(int i = 2; i <= 1000; i++)cout << gao(i) << endl;return 0;
}
好吧。。
n ^ 2的算法看起来实在是有些慢了。
如果n要到100W。 那么这个实在是没法做了。
所以还有更牛逼的方法吗？
答案是有的。
不过还要用到上面的那个999....999的结论
对于 1/ x
我们要找一个最小的999....999能被x整除
那么可以表示为
(10 ^ k - 1) % x == 0
加入x > 1
那么10 ^ k % x == 1
等等。 这个玩意为什么这么像欧拉函数的性质呢
对。确实如此。
令k = phi(x) 则必然满足上面那个等式
但我们要找最小的k，所以答案一定在k的因子中。
然后枚举因子就ok了
下面是我用该方法输出前1000项的循环小数的循环节长度
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <cmath>
#include <map>
#include <ctime>
#define MAXN 111111
#define INF 100000007
using namespace std;
int phi[100001];
void euler()
{phi[1] = 1;for(int i = 2; i <= 100000; i++)if(!phi[i]){for(int j = i; j <= 100000; j += i){if(!phi[j]) phi[j] = j;phi[j] = phi[j] / i * (i - 1);}}
}
long long fastmod(long long a, long long b, long long c)//a^b mod c
{long long ret = 1;a %= c;for (; b; b >>= 1, a = (a * a) % c)if (b & 1)ret = (ret * a) % c;return ret;
}
int gao(int x)
{while(x % 2 == 0) x /= 2;while(x % 5 == 0) x /= 5;if(x == 1) return 0;int k = phi[x];int ans = k;int m = (int)sqrt(k * 1.0);for(int i = 1; i <= m; i++)if(k % i == 0){if(fastmod(10, i, x) == 1) ans = min(ans, i);if(fastmod(10, k / i, x) == 1) ans = min(ans, k / i);}return ans;
}
int main()
{euler();for(int i = 2; i <= 1000; i++)printf("%d\n", gao(i));return 0;
}
下面我们测试一下n ^ 2和上面算法的时间比较吧
假设计算出1到10W所有1 / x的小数循环节长度
经过测试
n ^ 2算法：11s
上述算法：1.83s
那么1到100W呢
n ^ 2算法：太慢了。等不及跑，估计15分钟以上
上面的算法：18s
n^ 2算法被爆菊。。。
另外。 如果只要算一个x的话。而且当x为几十亿的话
直接模拟的方法很有可能超时。
不过这种用欧拉函数的方法却可以随便求。
单个的复杂度是sqrt(x) * log(x)的。
最后 我们来回到题目上、
是要求最大循环节的那个数。
经过打表我们发现。一般来讲，最大循环节的那个数一定是一个素数
不过我实在是不会证明。。