題目描述

給定一個數 x 和 n 個數 a_1...n 

求 x^a₁, x^a₂, ...,  x^a_n 對 999999999999999989 取模的值

輸入格式

第一行兩個數 x, n

第二行有 n 個數 a₁, ..., a_n 

輸出格式

輸出一行用空格分開的 n 個數： x^a₁, x^a₂, ...,  x^a_n 

Samples

2 3
2 10 31

4 1024 2147483648

提示

1 <= x <= 10⁹ 

1 <= n <= 10⁶ 

1 <= a_i <= 10¹² (1 <= i <= n)

 

測試點	x <=	n <=	ai (1 <= i <= n) <=
1	10	10	10
2	109	1000	1000
3-5	109	105	106
6-10	109	106	1012

備註

#include <stdio.h> #include

#define int uint32_t #define ll uint64_t #define lll __uint128_t

char *p1, *p2, buf[100]; #define getchar() (p1p2&&(p2=(p1=buf)+fread(buf,1,100,stdin),p1p2)?EOF:p1++) inline ll read() {static ll x;static char c;x=0;c=getchar();while(c<'0'||'9'<c)c=getchar();while('0'<=c&&c<='9')x=x10+c-48,c=getchar();return x;} void write(ll x) {if(x>9)write(x/10);putchar('0'+x%10);}

const ll MOD = 999999999999999989; const int S = 1048576;

ll X; int N; lll A, B, C, M; ll a[S+1], b[S+1]; ll ans;

main() { X = read(), N = read(); A = read(), B = read(), C = read(), M = read();

a[0] = b[0] = 1;
for (register int i = 1; i <= S; i++) {
	 a[i] = ((lll)a[i - 1] * X) % MOD;
}
for (register int i = 1; i <= S; i++) {
	 b[i] = ((lll)b[i - 1] * a[S]) % MOD;
}

while (N--) {
	A = (A * B + C) % M;
	ans ^= (lll)a[A - (A >> 20 << 20)] * b[A >> 20] % MOD;
}

write(ans); putchar('\n');

return 0;

}

原始資料

• Zero1 題號：b079
• Hydro 題號：Z1079
• Locale：zh_TW
• Display：open