202. 最幸运的数字 - AcWing题库

 

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;ll qmi(ll a, ll k, ll mod)
{ll res = 1;while(k){if(k & 1)res = (__int128)res * a % mod;a = (__int128)a * a % mod;k >>= 1;}return res;
}ll get_euler(ll x)
{ll res = x;for(int i = 2; i <= x / i; i ++){if(x % i == 0){res = res / i * (i - 1);while(x % i == 0)x /= i;}}if(x > 1)res = res / x * (x - 1);return res;
}int main()
{IOSint cnt = 0;ll L;while(cin >> L, L){L *= 9;int d = 1;while(L % (d * 2) == 0 && d * 2 <= 8)d *= 2;ll C = L / d;ll phi = get_euler(C), res = 2e18;if(__gcd(10ll, C) != 1)res = 0;for(ll i = 1; i * i <= phi; i ++){if(phi % i == 0){if(qmi(10, i, C) == 1){res = min(res, i);break;}if(qmi(10, phi / i, C) == 1){res = min(res, phi / i);}}}cout << "Case " << ++ cnt << ": " << res << endl;}return 0;
}