一个数的最大除数与质因数的关系

Question

问题如下： 给定两个数 n 和 k。对于区间 [1, n] 中的每个数字，您的任务是计算其不能被 k 整除的最大除数。打印所有这些除数的总和。注意：k 始终是素数。t=3*10^5,1<=n<=10^9, 2<=k<=10^9

我解决这个问题的方法是：对于 1 到 n 范围内的每个 i，所需的除数是 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。有人请帮忙。

Answer 1

就其本身而言，这更像是一个数学问题：如果 cur = [1..n]，正如您已经注意到的，最大除数 = dmax = cur 是，如果 cur % k != 0，否则 dmax 必须 < cur。从 k 我们知道它最多可以被其他素数整除...因为我们想确保 dmax 不能被 k 整除，我们可以用 while 循环来做到这一点...这当然也是更优雅的可能（因为由于质因数分解，dmax 必须再次成为质数）。

所以这应该看起来像这样（不保证只是输入 - 也许我在思考中错过了一些东西）：

#include <iostream>

int main() {
    unsigned long long n = 10;
    unsigned long long k = 2;

    for (auto cur_n = decltype(n){1}; cur_n <= n; cur_n++)
    {
        if (cur_n % k != 0) {
            std::cout << "Largest divisor for " << cur_n << ": " << cur_n << " (SELF)" << std::endl;
        } else {
            unsigned long long dmax= cur_n/k;

            while (dmax%k == 0)
                dmax= dmax/k;
            std::cout << "Largest divisor for " << cur_n << ": " << dmax<< std::endl;
        }
    }
}