社区讨论

关于一份代码的时间复杂度

学术版参与者 5已保存回复 13

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
13 条
当前快照
1 份
快照标识符
@lvn491vp
此快照首次捕获于
2024/05/01 09:06
2 年前
此快照最后确认于
2024/05/01 12:21
2 年前
查看原帖
rt,这是昨晚 div1 B2/div2 D2 的代码,疑似玄学复杂度,但是过了(
CPP
#include<bits/stdc++.h>
using namespace std;
int n,T,m,ans;
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0),cin>>T;
	while(T--){
		cin>>n>>m,ans=0;
		for(int s=2;s<=n;s++)
			for(int g=s;g<=n;g+=s)
				for(int x=max(1,s-m/g);x<=s&&x<=n/g;x++)
					if(__gcd(x,s-x)==1)
						ans++;
		cout<<ans<<'\n';
	}
	return 0;
}
1n,m2×1061\le\sum n,\sum m\le2\times10^6

回复

13 条回复,欢迎继续交流。

正在加载回复...