题目概述
考虑$x=\prod_{i}p_i^{a_i}$,$y=\prod_{i}p_i^{b_i}$.定义$x \bigotimes y$=$\prod_{i}p_i^{|a_i-b_i|}$,现在给定一个数列$a[1…n]$，求出
分析与解
首先通过$|a_i-b_i|=max(a_i,b_i)-min(a_i,b_i)$来理解这个定义本质是$\frac{lcm(a,b)}{gcd(a,b)}$,故进一步得到
那么不妨令
故
因此
由此可见后面这个$gcd$的部分可以通过对于一个数枚举其倍数预处理得到，其复杂度为
前面这个$s$的枚举是$O(n\sqrt n)$,但并不满。因此总复杂度是可以接受的。
此外，对于$s,t$并没有大小之分，但是需要保证$s \cdot gcd ,t \cdot gcd \leq n$,因此需要在上述计算中选择较小的$gcd$上限来运算。
注意事项
本题在考场上低级错误在于快速幂。
枚举因子时sqrt应当提前算出！
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 998244353;
#define MAXN 1001000
#define min(a,b) (a) < (b) ? (a) : (b)
int mread() {
int ret=0,f=1;
char c=getchar();
while(c<'0' || c>'9') {
if(c=='-')f=-1;
c=getchar();
}
do {
ret=ret*10+c-'0';
c=getchar();
} while('0'<=c && c<='9');
return ret*f;
}
LL quick_pow(LL a,LL b) {
LL ret=1;
while(b) {
if(b&1)ret=ret*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ret;
}
int gcd(int a,int b) {
if(b==0)return a;
return gcd(b,a%b);
}
LL b[MAXN];
int a[MAXN];
int n,c;
vector<LL> rela[MAXN];
LL my_pow[MAXN];
int main() {
LL sum=0;
LL now;
int s,t,qrt;
n=mread(),c=mread();
for(int i=1; i<=n; i++)a[i]=mread();
for(int i=1; i<=n; i++)my_pow[i]=quick_pow(i,c);
for(int i=1; i<=n; i++) {
now=0;
for(int j=i,k=1; j<=n; j+=i,k++) {
now=(now+1ll*a[j]*my_pow[k]%MOD+MOD)%MOD;
rela[i].push_back(now);
}
}
for(int i=1; i<=n; i++) {
qrt=sqrt((double)i);
for(int j=1; j<=qrt; j++) {
if(i%j!=0)continue;
s=j,t=i/j;
if(gcd(s,t)!=1)continue;
if(s!=t) {
b[i]=(b[i]+1ll*my_pow[t]*rela[s][min(n/s,n/t)-1]%MOD)%MOD;
b[i]=(b[i]+1ll*my_pow[s]*rela[t][min(n/s,n/t)-1]%MOD)%MOD;
} else b[i]=(b[i]+1ll*my_pow[s]*rela[s][min(n/s,n/t)-1]%MOD)%MOD;
}
}
for(int i=1; i<=n; i++)sum=sum^b[i];
printf("%lld\n",sum);
return 0;
}
|