【JZOJ A组】乘

Description

Input

Output

Sample Input

Sample Input1：
4 3 9 6
5 8 7 7

Sample Input2：
见下发文件中的 ex_pow2.in/out.

Sample Output

Sample Output1：
0

Data Constraint

思路

这道题很妙！
考虑 a 是定值, 而 b ≤ 10¹², 我们可以预处理 a 的 0…10⁶ 次方与 1 ∗ 10⁶, 2 ∗ 10⁶…10⁶ ∗ 10⁶ 次方, 询问时把 b 切成两半, 拼起来就是答案. 这样询问就是 O(1) 的. 复杂度 O(q + 10⁶).

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
ll a,p,q,k,b,l,m,c,ans,f[1000077],g[1000077];
int main()
{
	freopen("pow.in","r",stdin); freopen("pow.out","w",stdout);
	scanf("%lld%lld%lld%lld%lld%lld%lld%lld",&a,&p,&q,&k,&b,&l,&m,&c);
	f[0]=1; g[0]=1;
	for(int i=1; i<=1000007; i++) f[i]=f[i-1]*a%p;
	for(int i=1; i<=1000007; i++) g[i]=g[i-1]*f[1000000]%p;
	for(ll i=1; i<=q; i++)
	{
		b=(b*m+c)%l;
		ll x=b/1000000,y=b%1000000,s=g[x]*f[y]%p;
		ans=ans^s;
		if(i%k==0) printf("%lld\n",ans);
	}
}