社区讨论

关于在求最小公倍数的过程中取模

灌水区参与者 4已保存回复 12

讨论操作

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

当前回复
12 条
当前快照
1 份
快照标识符
@m6qcrdzk
此快照首次捕获于
2025/02/04 18:44
去年
此快照最后确认于
2025/11/04 23:05
4 个月前
查看原帖
对于一个序列 AA ,要判断 AA 中元素的最小公倍数能否整除 kk ,为什么在计算过程中对k取模是正确的?
具体例子:CF687B
CPP
typedef long long ll;
ll gcd(ll a, ll b){
	if(b==0)return a;
	return gcd(b, a%b);
}
int main(){
	int n, k;
	ll ans = 1, c;
	scanf("%d%d", &n, &k);
	for(int i = 1; i<=n; i++){
		scanf("%lld", &c);
		ans = ans/gcd(c, ans)*c%k;  // ???
		if(!ans){
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}

回复

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

正在加载回复...