题解：AT_abc414_e [ABC414E] Count A%B=C

解题思路

由于余数

c

于

a,b

密切相关，且当

a,b

一定时，

c

是唯一的，确定的。因此在统计答案是不需要枚举

c

。为了防止数对重复，我们规定：

a>b>c

。

再由题面知，

1\le c

，即

c

不能为

0

，也就是

a

不能是

b

的倍数的情况都成立。所以我们只要知道

(a,b)

（

b\le a

）的所有可能对数

sum

和

(a,b)

中

b\mid a

（

b

能整除

a

，

b\le a

）的对数

ans

。最终答案就是

sum-ans

。

解释一下上面为什么

a

可以与

b

相等：是因为当

a=b

时，

b\mid a

成立所以它在

sum

和

ans

里都统计了一次，在最终答案里抵消了相当于没统计，所以上面的

a

可以与

b

相等。

sum

的计算十分简单，因为在

a=i

时有

i

个数对，所以

sum=1+2+3+\cdots+N-1+N=\dfrac{(1+N)\times N}{2}

。时间复杂度

O(1)

。

但是

ans

就比较难在 1s 计算了，它的计算需要使用“数论分块”算法。在此，我就不献丑介绍了。不会的同学可以学习 P3935 Calculating 及其题解，它告诉了我们，如何在

\sqrt{N}

的时间里求出

1

到

N

内的约数个数和。

代码如下：

CPP

for(int l=1,r;l<=N;l=r+1){
    r=N/(N/l);
    ans+=(N/r)%mod*((r-l+1)%mod)%mod;
    ans%=mod;
}

最后只要注意取模并统计答案就行了。

时间复杂度：

O(\sqrt{N})

。

赛时代码

代码很短，不含注释只有 300 多 Byte。

CPP

#include<bits/stdc++.h>
#define int long long//记得开long long
using namespace std;
const int mod=998244353;//记得取模

int N,ans;

signed main(){
	cin>>N;
	for(int l=1,r;l<=N;l=r+1){//统计约数对数
		r=N/(N/l);
		ans+=(N/r)%mod*((r-l+1)%mod)%mod;
		ans%=mod;
	}
	int sum;//统计所有可能对数
	if(N%2) sum=(N+1)/2%mod*(N%mod)%mod;
	else sum=N/2%mod*((N+1)%mod)%mod;
	cout<<(sum-ans+mod)%mod;//输出答案
	
	return 0;
}

题解：AT_abc414_e [ABC414E] Count A%B=C

文章操作

解题思路

赛时代码

相关推荐

评论

题解：AT_abc414_e [ABC414E] Count A%B=C