c++ - 数和质因子关系的最大除数

问题如下:
给定两个数字n和k。对于间隔[1，n]中的每个数字，您的任务是计算不能被k整除的最大除数。打印所有这些除数的总和。
注意:k始终是质数。
t = 3 * 10 ^ 5,1
我对这个问题的看法:
对于1到n范围内的每个i，仅当i不是k的倍数时，所需的除数就是i本身。
如果我是k的倍数，那么我们必须找到一个数的最大除数并与k匹配。如果不匹配，那么这个除数就是我的答案。否则，我的答案就是第二大除数。

例如，取n = 10和k = 2，则范围1到10中的每个i所需的除数为1、1、3、1、5、3、7、1、9、5。这些除数之和为36。因此，ans = 36。

我的代码可用于一些测试用例，而对于某些测试用例则失败。

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

ll div2(ll n, ll k) {
if (n % k != 0 || n == 1) {
    return n;
}

else {
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ll aa = n / i;
            if (aa % k != 0) {
                return aa;
            }
        }
    }
}
return 1;
}



int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;

while (t--) {
    ll n, k;
    cin >> n >> k;
    ll sum = 0, pp;

    for (pp = 1; pp <= n; pp++) {
        //cout << div2(pp, k);
        sum = sum + div2(pp, k);
    }
    cout << sum << '\n';
 }

 }

有人可以帮我解决我做错的地方吗，还是可以建议我一些更快的逻辑来解决这个问题，因为我的一些测试用例显示了TIME LIMIT EXCEED

看完所有可能的解释后，我将代码修改如下:

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;

while (t--) {
    ll n, i;
    ll k, sum;
    cin >> n >> k;

    sum = (n * (n + 1)) / 2;

    for (i = k; i <= n; i = i + k) {
        ll dmax = i / k;

        while (dmax % k == 0) {
            dmax = dmax / k;
        }
        sum = (sum - i) + dmax;

    }
    cout << sum << '\n';

}

}

但是它仍然为3个测试用例提供了TIME LIMIT EXCEED。有人请帮忙。

最佳答案

就像其他人已经说过的一样，请查看约束:t=3*10^5,1<=n<=10^9, 2<=k<=10^9。

如果您的测试具有O(n)复杂度(可通过循环计算总和)，则最终需要执行t * n ~ 10^14。这太多了。

这个挑战是数学上的挑战。您需要使用两个事实:

正如您已经看到的

，如果i = j * k^s与j%k != 0一起使用，则最大除数为j；

sum_{i=1}^t i = (t * (t+1)) / 2

我们从

S = sum(range(1, n)) = n * (n+1) / 2

那么对于k * x形式的所有数字我们都添加了太多，我们来纠正一下:

S = S - sum(k*x for x in range(1, n/k)) + sum(x for x in range(1, n/k))
  = S - (k - 1) * (n/k) * (n/k + 1) / 2

继续输入k^2 * x形式的数字...然后k^p * x直到总和为空...

好的，人们开始编写代码，所以这是一个小的Python函数:

def so61867604(n, k):
    S = (n * (n+1)) // 2
    k_pow = k
    while k_pow <= n:
        up = n // k_pow
        S = S - (k - 1) * (up * (up + 1)) // 2
        k_pow *= k
    return S

并在这里行动https://repl.it/repls/OlivedrabKeyProjections

关于c++ - 数和质因子关系的最大除数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/61867604/