1007: Pass!
const int mod = 998244353;
inline int ksm(int a, int b) {
int res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
inline int inv(int x) {
return ksm(x, mod - 2);
}
/*
1 0
0 1
10 2
90 3
910 4
9090 5
90910 6
909090 7
9090910
90909090
909090910
fi = fi-1 * 9 + fi-2 * 10
fi + fi-1 = 10^x
if(i & 1) fi = (fi-1 - 1) * 10
else fi = (fi-1 + 1) * 10
1、假设x是偶数项 -> x + (x - 1) * 10 = 10^m(m & 1 == 0)
2、假设x是奇数项 -> x + (x + 1) * 10 = 10^m(m & 1 == 1)
通用即将10改为(n - 1)
TLE:
优化
1、偶数项优化:即x + (x - 1) * 10 = 100^m -> ans = 2 * m
2、奇数项优化:变为 x * inv(n - 1) + 1 + x = 100^m -> ans = 2 * m + 1
还是不行
优化:将两项放在一起 -> 显然两项都是100^m,一起求
还是不行
优化:将map -> unordered_map
ok! 评测姬真---
BGSG:*/
int log(int a, int b, int ans1, int ans2) {
int m = sqrt(mod + 0.5), v = inv(ksm(a, m));
unordered_map<int, int> mp; mp[1] = 0;
for(int i = 0, e = 1; i < m; ++ i, e = e * a % mod) {
if(e == ans1) return i * 2;
if(e == ans2) return i * 2 + 1;
if(!mp.count(e)) mp[e] = i;
}
for(int i = 0, mul = 1; i < m; ++ i, mul = mul * v % mod) {
if(mp.count(ans1 * mul % mod)) return (i * m + mp[ans1 * mul % mod]) * 2;
if(mp.count(ans2 * mul % mod)) return (i * m + mp[ans2 * mul % mod]) * 2 + 1;
}
return -1;
}
void run() {
//printf("%lld\n", ksm(10, 196003445));
int n = rd(), x = rd(), pre = 1;
/*for(int i = 1; i <= 10; ++ i) {
if(i & 1) printf("%lld\n", pre = (pre - 1) * (n - 1));
else printf("%lld\n", pre = (pre + 1) * (n - 1));
}*/
if(x == 1) {
puts("0");
return ;
}
if(x == 0) {
puts("1");
return ;
}
int y = (x - 1) * (n - 1) % mod;
int ans1 = (x + y) % mod;
//x = (x + 1) * (n - 1) % mod;
//(prex - 1) * (n - 1) = x
//prex = x / (n - 1) + 1
y = (x * ksm(n - 1, mod - 2) + 1) % mod;
int ans2 = (x + y) % mod;
int res = log((n - 1) * (n - 1) % mod, (x + y) % mod, ans1, ans2);//偶数项
printf("%lld\n", res % mod);
/*x = (x + 1) * (n - 1) % mod;
y = (x - 1) * (n - 1) % mod;
res = log((n - 1) * (n - 1) % mod, (x + y) % mod);//奇数项
if(res != -1) printf("%lld\n", (res * 2 % mod - 1 + mod) % mod);
else puts("-1");*/
return ;
}
signed main() {
int t = rd();
while(t--) run();
return 0;
}