由于m 可能很大所以加上快速乘
C++ 代码
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
bool ok;
ll L;
int cntf, ans;
struct Node{
int num, cnt;
} fact[2000];
int gcd(int a, int b) {
return b ? gcd(b, a % b): a;
}
ll qmul(ll a, ll b, ll m) {
ll ans = 0;
while (b) {
if (b & 1) {
ans = (ans + a) % m;
}
a = (a << 1) % m;
b >>= 1;
}
return ans;
}
ll qpow(ll a, ll b, ll m) {
ll ans = 1;
while (b) {
if (b & 1) {
//这里m可能很大所以要用快速乘
ans = qmul(ans, a, m) % m;
}
a = qmul(a, a, m) % m;
b >>= 1;
}
return ans;
}
void dfs(int u, ll p, ll m) {
if (ok) return;
if (u >= cntf) {
//检查是否合格
if (qpow(10, p, m) == 1) {
ok = true;
ans = p;
}
return;
}
for (int i = 0; i <= fact[u].cnt; i++) {
dfs(u + 1, p, m);
p *= fact[u].num;
}
}
ll euler(ll n) {
ll phi = n;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
phi = phi / i * (i - 1);
while (n % i == 0) n /= i;
}
}
//防止最后是质数
if (n > 1) {
phi = phi / n * (n - 1);
}
}
int main() {
int t = 1;
while (scanf("%lld", &L), L) {
//初始化变量
ans = 0;
ok = false;
cntf = 0;
int d = gcd(L, 8);
ll mod = 9 * L / d;
//cout << phi << endl;
//求出9L/d的欧拉值
ll phi = euler(mod);
//cout << phi << endl;
//求出phi的约数
for (int i = 2; i <= phi / i; i++) {
if (phi % i == 0) {
int cnt = 0;
while (phi % i == 0) cnt++, phi /= i;
fact[cntf].num = i;
fact[cntf++].cnt = cnt;
}
}
if (phi > 1) {
fact[cntf].num = phi;
fact[cntf++].cnt = 1;
}
//dfs求出所有约数
dfs(0, 1, mod);
printf("Case %d: %d\n", t++, ans);
}
return 0;
}