NOIP2018模拟11.01 乘

wjh15101051's space

卧薪尝胆，厚积薄发。

NOIP2018模拟11.01 乘

Date: Sun Nov 04 07:51:17 CST 2018

In Category: NoCategory

Description：

多次询问 $a^{b_i}$ 。

$1\leqslant n\leqslant 10^7,1\leqslant b_i\leqslant 10^{12}$

Solution：

预处理出 $a$ 的 $[1,10^6]$ 的幂和 $a^{10^6}$ 的 $[1,10^6]$ 的幂，询问时把两个合并即可。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

ll a,mod,q,k;

ll b0,l,m,c;

#define MAXN 10000010

ll b[MAXN];

#define MAX 1000010

ll power1[MAX],power2[MAX];

int main()

{

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

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

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

	a %= mod;

	power1[0] = 1;

	for(ll i = 1;i < MAX;++i)power1[i] = power1[i - 1] * a % mod;

	power2[0] = 1;power2[1] = power1[1000000];

	for(ll i = 2;i < MAX;++i)power2[i] = power2[i - 1] * power2[1] % mod;

	scanf("%lld%lld%lld%lld",&b[0],&l,&m,&c);

	for(ll i = 1;i <= q;++i)b[i] = (b[i - 1] * m + c) % l;

	ll ans = 0;

	for(ll i = 1;i <= q;++i)

	{

		ll res = power2[b[i] / 1000000] * power1[b[i] % 1000000] % mod;

		ans ^= res;

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

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}

In tag: 玄学

wjh15101051