定理不会证所以直接讲应用。
CF776E The Holmes Children
随便证一下（打表）得，\(f\) 函数为欧拉函数，那么 \(g(n)=n\)，模拟大 \(F\) 函数得到答案。
时间复杂度证明
发现大 $F$ 函数在算一个套娃 $\phi$ 值。由于欧拉函数值必为偶数，小于偶数 \(x\) 的所有偶数定与 \(x\) 不互质，所以我们得知大 \(F\) 最多会算 \(log_2\) 次。
点击查看代码
//author : yhy
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using Pii = pair<LL, LL>;
LL n, k;
LL phi(LL x) {
LL ans = x;
for (LL i = 2; i * i <= x; i++) {
bool fl = 0;
for (; x % i == 0; fl = 1, x /= i) {
}
fl && (ans = ans / i * (i - 1));
}
x > 1 && (ans = ans / x * (x - 1));
return ans;
}
LL f(LL x, LL k) {
if (x == 1 || k <= 0) {
return x;
}
return f(phi(x), k - 2);
}
signed main() {
cin.tie(0)->ios::sync_with_stdio(0);
cin >> n >> k, cout << f(n, k) % 1000000007;
return 0;
}
AT_abc222_g 222
常见的 Trick。
首先式子 \(k=222\cdots222\)，如果 \(k\) 是 \(2\) 的倍数就将 \(k\) 除二，然后：
\[k\mid111\cdots111 \]\[9k\mid999\cdots999 \]\[9k\mid10^x-1 \]\[10^x-1\equiv 0(\bmod 9k) \]\[10^x\equiv1(\bmod 9k) \]如果 \(\gcd(9k, 10)=1\) 根据欧拉定理 \(10^{\phi(9k)}\equiv(\bmod9k)\)，但题目要求最小，随便证一下得 \(x\mid \phi(9k)\)。
否则无解。
点击查看代码
// author : yhy
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using Pii = pair<LL, LL>;
LL T, n;
LL phi(LL x) {
LL ans = x;
for (LL i = 2; i * i <= x; i++) {
bool fl = 0;
for (; x % i == 0; fl = 1, x /= i) {
}
fl && (ans = ans / i * (i - 1));
}
x > 1 && (ans = ans / x * (x - 1));
return ans;
}
LL qpow (LL a, LL n, LL M) {
LL r = 1, w = a;
for (LL i = 1; i <= n; i <<= 1) {
n & i && (r = r * w % M);
w = w * w % M;
}
return r;
}
signed main() {
cin.tie(0)->ios::sync_with_stdio(0);
for (cin >> T; T--;) {
cin >> n, n = (n & 1 ? n : n / 2);
if (__gcd(9 * n, 10LL) != 1) {
cout << "-1\n";
continue;
}
set<LL> st;
LL t = phi(9 * n), ans = -1;
for (LL i = 1; i * i <= t; i++) {
t % i == 0 && (st.insert(i), st.insert(t / i), 0);
}
for (LL x : st) {
if (qpow(10, x, 9 * n) == 1) {
ans = x;
break;
}
}
cout << ans << '\n';
}
return 0;
}