Sample Output

Sample Output1：

0
做法（转自JZOJ）：考虑 a 是定值, 而 b ≤ 1012 , 我们可以预处理 a 的 0...106 次方与 1 ∗ 106 , 2 ∗ 106 ...106 ∗ 106 次 方, 询问时把 b 切成两半, 拼起来就是答案. 这样询问就是 O(1) 的. 复杂度 O(q + 106 ).

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <string>

 #define LL long long

 #define N 1000007

 using namespace std;

 LL a,p,q,k;

 LL b,m,l,C,b1;

 LL ans,mia[N],la[N];

 LL ksm(LL a,LL b){

     LL root=,base=a;

     while(b){

         if (b&) root*=base,root%=p;

         base*=base;

         base%=p;

         b>>=;

     }

     return root;

 }

 int main(){

     freopen("pow.in","r",stdin);

     freopen("pow.out","w",stdout);

     scanf("%lld%lld%lld%lld",&a,&p,&q,&k);

     scanf("%lld%lld%lld%lld",&b,&l,&m,&C);

     mia[]=;

     la[]=;

     LL g=;

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

         mia[i]=(mia[i-]*a)%p,la[i]=ksm(mia[i],g)%p;

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

         b1=(b*m+C)%l;

         ans=ans^((mia[b1%g]*la[b1/g])%p);

         if (i%k==)    printf("%lld\n",ans);

         b=b1;

     }

 }