[COGS 2745] 求GCD之和
book
归档:
OI
flag
题目描述
原题地址:COGS
题目是在济南集训时候的比赛题
题意:求$\sum^n_ {i = 1}\sum_{j=1}^m\gcd(i,j)\mod998244353$
解法
算法一
暴力计算,复杂度$O(n^2\log n)$,期望得分40。
代码没必要上了吧。。
算法二
大常数AC
- 枚举从$n$到$1$的所有数,考虑到以$i$为约数的数的对数为$\lfloor\frac{n}{i}\rfloor\times\lfloor\frac{m}{i}\rfloor$对。
- 又可知若以$i$为最大公约数的数的对数为$m$,则$i$对答案的贡献是$i\times m$。
因此我们需要进一步细化1中的数的对数。
我们可以从$2i$开始,减去所有以$i$的倍数为约数的数对的数目,这样就求得以$i$为最大公约数的数对的个数,结合2的方法,计算贡献,累加。
代码:
#include<bits/stdc++.h>
using namespace std;
const int p = 998244353;
long long q[10000010];
int n,m;
int main()
{
freopen("hoip.in","r",stdin);
freopen("hoip.out","w",stdout);
int i,j;
long long s = 0;
scanf("%d%d",&n,&m);
if(n > m) swap(n,m);
for(i = n;i >= 1;i--)
{
q[i] = 1ll * (n / i) * (m / i);
for(j = i + i;j <= n;j += i) q[i] -= q[j];
s += q[i] * i;
}
printf("%d",s % p);
return 0;
}
复杂度。。算不出来。。不过显然是大于$O(n)$的qwq
以上是青岛二中神犇zyb的解法
无限%zyb dalao,一试二试都是rk1 %%%。
算法三
用莫比乌斯函数容斥,加上狄利克雷卷积优化,复杂度$O(n)$
根本没有听懂,以后再填qwq
坑填上啦!
navigate_before
[COGS 2632] [HZOI 2016] 数列操作d
[置顶] 最近(联赛前)待填坑
navigate_next