CF1912D Divisibility Test 题解

FFTotoro · 2023-12-16 19:14:29 · 题解

小学奥数判断整除的几种便捷方法。

考虑三种操作的实质：

• 取最后 k 位：当 b^k\bmod n=0 时可以使用该方法；

  证明：显然 b^{k+d}\bmod n=0(d\ge 0)，所以更高位上的数可以不用考虑，直接考虑后 k 位即可；

• 证明：有 $xb^{dk}\equiv xb^k\equiv x\pmod n(d\ge 0)$，于是将系数 $b^k$ 视为 $1$，$k$ 位一组求和是正确的；下面的证明类似，就是把 $1$ 换成 $-1$；

显然 k 最大为 n。枚举即可；注意判断无解。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int b,n; cin>>b>>n;
    long long c=1; bool f=false;
    for(int k=1;k<=n&&!f;k++){
      if((c*=b)%=n;!c)cout<<"1 "<<k<<'\n',f=true;
      if(c==1)cout<<"2 "<<k<<'\n',f=true;
      else if(c==n-1)cout<<"3 "<<k<<'\n',f=true;
    }
    if(!f)cout<<"0\n"; // 无解
  }
  return 0;
}