又是一道水绿。
刚刚小学毕业的数学 idiot——我释怀地笑了。
第一种很好判断，当 $b^k$ 为 $n$ 的倍数时，取基数为 $b$ 的能被 $n$ 整除的整数 $c$ 的最后 $k$ 位数显然能被 $n$ 整除。
第二种也不难，当 $b^k \equiv 1 \pmod n$ 时，取以 $b$ 为底数的能被 $n$ 整除的整数 $c$ 的 $k$ 位数的各组之和能被 $n$ 整除。
为什么呢？
令 $a_1,a_2,\dots,a_l$ 为 $c$ 从低位到高位各个 $k$ 位数，则 $c=\sum _ {i=1} ^ {l} a_i \times 10^{(i-1)k}$，而和 $d$ 为 $\sum _ {i=1} ^ {l} a_i$。∵$10^{(i-1)k}\equiv 1 \pmod n$。于是 $c=\sum _ {i=1} ^ {l} a_i \times 10^{(i-1)k} \equiv \sum _ {i=1} ^ {l} a_i \times 1 \pmod n$。∴$c \equiv d \pmod n$。
第三种也很好判断，按第二种的方法，能推出式子。当 $b^k \equiv -1 \pmod n$ 时，取以 $b$ 为底数的能被 $n$ 整除的整数 $c$ 的 $k$ 位数的各组之和能被 $n$ 整除。
令 $a_1,a_2,\dots,a_l$ 为 $c$ 从低位到高位各个 $k$ 位数，则 $c=\sum _ {i=1} ^ {l} a_i \times 10^{(i-1)k}$，而和 $d$ 为 $\sum _ {i=1} ^ {l} (-1)^i\times a_i$。∵$10^{(i-1)k}\equiv -1 \pmod n$。于是 $c=\sum _ {i=1} ^ {l} a_i \times 10^{(i-1)k} \equiv \sum _ {i=1} ^ {l} a_i \times (-1)^i \pmod n$。∴$c \equiv d \pmod n$。
My code：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,b,n;
ll power;
int main(){
cin>>t;
while(t--){
cin>>b>>n;
power=1;
bool f=0;
for(int k=1;k<=n&&!f;k++){
power=power*b%n;
if(!power)cout<<"1 "<<k<<'\n',f=1;
else if(power==1)cout<<"2 "<<k<<'\n',f=1;
else if(power==n-1)cout<<"3 "<<k<<'\n',f=1;
}
if(!f) cout<<"0\n";
}
return 0;
}