bzoj4891 [Tjoi2017]龙舟

bzoj4891 [Tjoi2017]龙舟

​​ 题目描述

加里敦大学有一个龙舟队，龙舟队有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意义下的逆元，如果不存在逆元我们认为队伍发挥失常)。现在是这个赛季的比赛安排情况，现在教练组想知道各队的在比赛中表现情况。

输入输出格式

输入格式： 第一行输入三个个整数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的比赛中出战

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

输入输出样例

输入样例#1： 复制

2 3 3 5 2 3 3 2 3 2 3 2 1 4 2 4 1 7 输出样例#1： 复制

3 -1 4 说明

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

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

考虑如何分解质因数即可

预备知识 o(1) 快速乘

因为模数在long long 范围所以会爆longlong 这时候可以采用log的方式边模边乘

也可以用o1快速乘

考虑模拟取模的过程 那便是x*y-x*y/mod*mod

那么因为我们直到这个他们的这个差是在 long long范围内的所以肯定存的下 那么前面的x*y就让他自然溢出 相当于对2^31-1取模 因为我差不会超过这个 所以并不影响 影响的只会是有可能溢出导致的多进一位1 那么可能变成负数 我再+mod即可

然后就是miller rabin算法 快速判断素数

如何判断素数 考虑费马小定理 但是费马小定理的逆定理不一定成立 也就是满足所有与n互质的数的n-1次方%n=1的情况下 这个n也不一定是质数 因为这是充分不必要条件

考虑假如n是一个奇素数n-1表示成2^s*r 那么一定满足a^r同余1(mod n)

对某个j(0≤j ≤s －1， j∈Z) 等式 a^(2^j*r) ≡－1(mod n) 那么我每回就可以随机一个x且这个x<=n-2 然后去验证即可 这个x一定和n-2互质

在代码实现的时候为了方便一些考虑先判断是否是+-1 如果不是的话 后面如果不停的平方出现1 了 那么说明一定是有问题的 因为不满足定义的式子的要求x^2≡1(mod n)但是等于-1的情况下就一定可以说明下一次再翻倍的时候一定会变成1 所以直接退出就行了 算法 判断不是素数的时候一定不是素数 如果算法判定是素数的时候 那么很大可能是素数 实际应用中正确率非常高

最后再是Pollard_rho算法

考虑有了上面的铺垫 然后我们考虑随机一个数 然后来判断他是否是我的一个因数 注意并不要求质因数 只要是我的一个因数 那么我就继续去分解这个因数 然后同时再分解n/tmp这个因数直到用miller rabin判断这个是一个素数或者=1的时候就停止 这时候这个大数就被分解成了质因数相乘的形式

具体怎么做考虑每次随机一个数效率太低了

算法构造了一个函数 xi=(xi-1^2+a) mod n x0,a分别随机

然后每次用这个函数每次随机一个x1出来 然后由x1构造x2，使得｛p可以整除x1-x2 && x1-x2不能整除n｝则p=gcd（x1-x2，n）就是我们想要的答案 当然p不能=1 如果p=1那么继续随机即可

可以考虑这个函数一定是循环的我有可能这个函数一直无法生成我想要的因数然后进入了圈那么就需要快速判圈 floyd判圈法 考虑两个人在同一个跑到 b是a的两倍速度在跑那么 当b追上a的时候显然陷入了一个循环 那么我们只需要构造这个b这个函数 使得他是a这个函数的再平方 应该就okay了

时间复杂度为n14 n 1 4

#include#include#define ll long long#define lb long double#include#define eps 1e-8using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline ll read(){ ll x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=10010;inline ll mul(ll a,ll b,ll mod){static ll tmp;tmp=0; tmp=(a*b-(ll)((lb)a/mod*b)*mod)%mod; return tmp<0?tmp+mod:tmp;}inline ll ksm(ll b,ll t,ll mod){static ll tmp;tmp=1; for (;t;b=mul(b,b,mod),t>>=1) if (t&1) tmp=mul(tmp,b,mod);return tmp;}inline ll abs1(ll x){return x<0?-x:x;}inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}inline bool check(ll g,ll y,int cnt,ll mod){static ll x; x=ksm(g,y,mod);if (x==1||x==mod-1) return 1; for (int i=1;i<=cnt;++i){ x=mul(x,x,mod);if (x==1) return 0;if (x==mod-1) return 1; }return 0;}inline bool miller_rabin(ll x){static ll y;static int cnt; if (x==2) return 1;if ((x&1)==0) return 0;cnt=0; y=x-1;while((y&1)==0) ++cnt,y>>=1; for (int i=1;i<=10;++i) if(!check(rand()%(x-2)+1,y,cnt,x)) return 0; return 1;}inline ll inc(ll x,ll v,ll mod){return x+v>=mod?x+v-mod:x+v;}inline int pollard_rho(ll a,ll mod){ ll x=rand()%mod,y=x,k=2,g=1; for (int i=1;g==1;++i){ x=inc(mul(x,x,mod),a,mod); g=gcd(abs1(x-y),mod);if (i==k) {k<<=1;y=x;} }return g;}ll ans,tmp[N],b[N],ab[22][N],prime[N];int cnt,nm[N];inline void findfac(ll x){ if (x==1) return;if (miller_rabin(x)) {tmp[++cnt]=x;return;} ll tmp=x;while(x==tmp) tmp=pollard_rho(rand()%(x-1)+1,x); findfac(tmp);findfac(x/tmp);}int n,m,k;int main(){ freopen("bzoj4891.in","r",stdin); srand(20010820); n=read();m=read();k=read(); for (int i=1;i<=m;++i) b[i]=read(); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) ab[i][j]=read(); for (int owo=1;owo<=k;++owo){static int id;static ll M; id=read();M=read();cnt=0;findfac(M); sort(tmp+1,tmp+cnt+1);ll phi=M;int tot=0; for (int i=1;i<=cnt;++i){ if(tmp[i]!=tmp[i-1]){ prime[++tot]=tmp[i];nm[tot]=0;phi=phi-phi/tmp[i]; } }ll inv=1;ans=1; for (int i=1;i<=m;++i) {static ll tp; tp=b[i]; for (int j=1;j<=tot;++j){ while(tp%prime[j]==0) tp/=prime[j],++nm[j]; }ans=mul(ans,tp,M); } for (int i=1;i<=m;++i){static ll tp; tp=ab[id][i]; for (int j=1;j<=tot;++j){ while(tp%prime[j]==0) tp/=prime[j],--nm[j]; }inv=mul(inv,tp,M); }bool flag=0; for (int i=1;i<=tot;++i) if (nm[i]<0) {puts("-1");flag=1;break;}if (flag) continue; for (int i=1;i<=tot;++i) if (nm[i]) ans=mul(ans,ksm(prime[i],nm[i],M),M); ans=mul(ans,ksm(inv,phi-1,M),M);printf("%lld\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。