UVA13131

标签：int dfrac 复杂度 枚举 times 因数 UVA13131

前言

题目传送门！

更好的阅读体验？

这题是假灰题，建议加上翻译并评红。

题意

给定 \(n\) 与 \(k\)，求 \(n\) 的因数中，所有不能整除 \(k\) 的数的和。

思路

枚举 \(n\) 所有因数 \(i\)，如果 \(i\not\equiv0\pmod{k}\)，就统计。

但是，如果用 \(O(n)\) 的时间硬枚举因数，总的时间复杂度就是 \(O(T \times n)\)，炸掉了。

所以我们需要优化。

如果 \(i\) 是 \(n\) 的因数，则 \(\dfrac{n}{i}\) 也是 \(n\) 的因数。

这样，我们仅需枚举到 \(\sqrt{n}\)，总时间复杂度 \(O(T \times \sqrt{n})\)，轻松通过。

坑点

如果 \(i \times i = n\)，说明 \(\dfrac{n}{i} = i\)，此时仅需判断 \(i\)，无需判断 \(\dfrac{n}{i}\)。

完整代码

#include <iostream>
#include <cstdio>
using namespace std;
void solve()
{
	int n, k, sum = 0;
	scanf("%d%d", &n, &k);
	for (int i = 1; i*i <= n; i++)
		if (n % i == 0) 
		{
			if (i % k != 0) sum += i;
			//如果不是平方数，(n / i) 才需要检验。 
			if (i * i != n && (n / i) % k != 0) sum += (n / i); 
		}
	printf("%d\n", sum);
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

首发：2022-04-20 10:15:45

标签：int,dfrac,复杂度,枚举,times,因数,UVA13131
From： https://www.cnblogs.com/liangbowen/p/16622841.html