BZOJ4891:[TJOI2017]龙舟(Pollard-Rho,exgcd)

2022-06-12 00:29:48

Description

加里敦大学有一个龙舟队，龙舟队有n支队伍，每只队伍有m个划手，龙舟比赛是一个集体项目，和每个人的能力息息相关，但由于龙舟讲究配合，所以评价队伍的能力的是一个值c = (b1*b2...*bm)/(a1*a2...*am),其中bi表示第i个位置标准能力值，ai表示在队伍中第i个位置的划手的能力值。最后通过约分，我们会得到c= B/A,其中gcd(B,A)=1,即A, B是互质的，

但是由于比赛现场的情况不一样，我们认为在现场压力为M的情况下，队伍最后的表现情况认为是C=1(mod M)我们规定在模M的条件下1/x = y，其中y满足xy=1(mod M)并且y是大于等于0,并且小于M的值，如果不存在这样的y我们就认为在M的条件下这支队伍会发挥失常(即y是x在模M意义下的逆元，如果不存在逆元我们认为队伍发挥失常)。现在是这个赛季的比赛安排情况，现在教练组想知道各队的在比赛中表现情况。

Input

第一行输入三个个整数n, m，k，表示有n支队伍，每支队伍有m个人组成，有k场比赛

第二行输入m个整数，第i个表示表征第i个位置的标准能力值为bi

第3行到第n +2行，共n行，每行有m个数，第2+i行第j个数表示第i支队伍的第j个位置的划手的能力值

第n + 3行到第n + k + 2行，共n行，每行有两个数x,M，分别表示第x支队伍会在压力为M的比赛中出战

Output

共k行，第i行表示在第i个参赛安排种队伍的现场表现情况C，如果出现队伍发挥失常，输出“-1”

Sample Input

2 3 3
5 2 3
3 2 3
2 3 2
1 4
2 4
1 7

Sample Output

3
-1
4

HINT

对于20%的数据，1<M,ai,bi<10^8,m<=100

对于100%的数据，1<M,ai,bi<2*10^8,m<=10000,n<=20,k<=50

Solution

$Pollard-Rho$。

首先对于每次询问，先把$M$质因数分解一下，然后在分子和分母上分别用那些质因数去分解，并且开个桶存一下质因子的出现情况。如果分解完某个质因子在分母上还存在（也就是桶中的个数为负数），那显然$M$和分母不互质，无解输出$-1$。

否则就可以用$exgcd$把逆元给解出来，然后输出就好了QwQ

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<map>

 #include<algorithm>

 #define N (10009)

 #define LL long long

 using namespace std;

 LL n,m,k,x,y,c,M,cnt,ans,inv;

 LL a[][N],b[N],Num[N],Keg[N];

 LL prime[]={,,,,,,,,};

 LL Mul(LL a,LL b,LL MOD)

 {

     LL tmp=a*b-(LL)((long double)a*b/MOD+0.1)*MOD;

     return tmp<?tmp+MOD:tmp;

 }

 LL Qpow(LL a,LL b,LL MOD)

 {

     LL ans=;

     while (b)

     {

         if (b&) ans=Mul(ans,a,MOD);

         a=Mul(a,a,MOD); b>>=;

     }

     return ans;

 }

 LL gcd(LL a,LL b) {return b==?a:gcd(b,a%b);}

 void exgcd(LL a,LL b,LL &x,LL &y)

 {

     if (!b) {x=; y=; return;}

     exgcd(b,a%b,y,x); y-=x*(a/b);

 }

 bool Miller_Rabin(LL n)

 {

     if (n==) return ;

     if (n< || n%==) return ;

     LL m=n-,l=;

     while (m%==) m>>=,l++;

     for (int i=; i<; ++i)

     {

         LL p=prime[i],w=Qpow(p,m,n);

         if (w== || w==n- || p==n) continue;

         for (int j=; j<=l; ++j)

         {

             LL u=Mul(w,w,n);

             if (u== && w!= && w!=n-) return ;

             w=u;

         }

         if (w!=) return ;

     }

     return ;

 }

 LL Pollard_Rho(LL n,LL c)

 {

     LL x=rand()%n,y=x,p=,k=;

     for (int i=; p==; ++i)

     {

         x=(Mul(x,x,n)+c)%n;

         p=x>y?x-y:y-x;

         p=gcd(p,n);

         if (i==k) y=x, k+=k;

     }

     return p;

 }

 void Solve(LL n)

 {

     if (n==) return;

     if (Miller_Rabin(n)) {Num[++cnt]=n; return;}

     LL t=n;

     while (t==n) t=Pollard_Rho(n,rand()%(n-)+);

     Solve(t); Solve(n/t);

 }

 int main()

 {

     scanf("%lld%lld%lld",&n,&m,&k);

     for (int i=; i<=m; ++i)

         scanf("%lld",&b[i]);

     for (int i=; i<=n; ++i)

         for (int j=; j<=m; ++j)

             scanf("%lld",&a[i][j]);

     while (k--)

     {

         for (int i=; i<=cnt; ++i) Keg[i]=;

         cnt=; ans=; inv=;

         scanf("%lld%lld",&x,&M);

         Solve(M);

         sort(Num+,Num+cnt+);

         cnt=unique(Num+,Num+cnt+)-Num-;

         for (int i=; i<=m; ++i)

         {

             LL tmp=b[i];

             for (int j=; j<=cnt; ++j)

                 while (tmp%Num[j]==) Keg[j]++, tmp/=Num[j];

             ans=Mul(ans,tmp,M);

         }

         for (int i=; i<=m; ++i)

         {

             LL tmp=a[x][i];

             for (int j=; j<=cnt; ++j)

                 while (tmp%Num[j]==) Keg[j]--, tmp/=Num[j];

             inv=Mul(inv,tmp,M);

         }

         bool flag=true;

         for (int i=; i<=cnt; ++i)

             if (Keg[i]<) flag=false;

         if (!flag) {puts("-1"); continue;}

         for (int i=; i<=cnt; ++i)

             if (Keg[i]) ans=Mul(ans,Qpow(Num[i],Keg[i],M),M);

         exgcd(inv,M,x,y); inv=(x%M+M)%M;

         printf("%lld\n",Mul(ans,inv,M));

     }

 }

码农公寓