https://uva.onlinejudge.org/external/119/p11916.pdf
令m表示不能染色的格子的最大行号
设>m行时可以染k种颜色的格子数有ck个，恰好有m行时可以染k种颜色的格子数有ckm个
分m行、m+1行、>m+1行讨论
如果是m行：k^ckm * (k-1)^(n*m-b-ckm) = r
如果是m+1行， k^ckm * (k-1)^(n*m-b-ckm) * k^(ck-ckm) * (k-1)^(n-(ck-ckm)) = r
如果>m行，k^ckm * (k-1)^(n*m-b-ckm) * k^(ck-ckm) * (k-1)^(n-(ck-ckm)) * k^n^mm = r ，ans=m+1+mm
求mm用bsgs
注意：
1、后面注意b=0的情况，当b=0时，n*m-b-ckm 是负数，快速幂死循环，注意特判
2、用bsgs时，A^B≡C mod P，其中A=k^n，不能令A=k，求出的B再除以n
#include<map>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; const int mod=1e8+; #define N 501 struct node
{
int x,y;
}e[N+]; map<int,int>mp; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} int Pow(int a,long long b)
{
int res=;
for(;b;b>>=,a=1LL*a*a%mod)
if(b&) res=1LL*res*a%mod;
return res;
} int get_inv(int a)
{
return Pow(a,mod-);
} int BSGS(int a,int b,int p)
{
mp.clear();
int m=sqrt(p);
mp[b]=;
for(int i=;i<=m;++i)
{
b=1LL*b*a%mod;
mp[b]=i;
}
int am=Pow(a,m);
int mul=;
for(int i=;i<=m;++i)
{
mul=1LL*mul*am%mod;
if(mp.find(mul)!=mp.end()) return i*m-mp[mul];
}
return -;
} bool cmp(node p,node q)
{
if(p.y!=q.y) return p.y<q.y;
return p.x<q.x;
} int main()
{
int T;
int n,k,b,r;
int m,x,y;
int ck,ckm;
int a,rr;
int ans;
read(T);
for(int t=;t<=T;++t)
{
read(n); read(k); read(b); read(r);
ck=ckm=n; m=;
for(int i=;i<=b;++i)
{
read(e[i].x); read(e[i].y);
if(e[i].x==) ck--,ckm--;
m=max(m,e[i].x);
}
sort(e+,e+b+,cmp);
e[b+].x=e[b+].y=-;
for(int i=;i<=b;++i)
if(!(e[i].y==e[i+].y && e[i].x==e[i+].x-))
{
ck++;
if(e[i].x!=m) ckm++;
}
if(m)
{
rr=1LL*Pow(k,ckm)*Pow(k-,1LL*n*m-b-ckm)%mod;
if(rr==r)
{
printf("Case %d: %d\n",t,m);
continue;
}
rr=1LL*rr*Pow(k,ck-ckm)%mod;
rr=1LL*rr*Pow(k-,n-(ck-ckm))%mod;
}
else rr=Pow(k,n);
if(rr==r)
{
printf("Case %d: %d\n",t,m+);
continue;
}
r=1LL*r*get_inv(rr)%mod;
a=BSGS(Pow(k-,n),r,mod);
printf("Case %d: %d\n",t,a+m+);
}
return ;
}