最大除数与质因数的关系

Question

问题如下：给定两个数n和k，对于区间[1，n]中的每一个数，你的任务是计算其不被k整除的最大除数，并打印出所有这些除数的总和。

我对这个问题的处理方法是:对于1到n范围内的每一个i，所需的除数是i本身，只有当这个i不是k的倍数时，才需要找到一个数字的最大除数，并与k匹配，如果不匹配，那么这个除数就是我的答案，否则，第二大除数就是我的答案。

例如,取n=10,k=2,在1到10的范围内,每一个i所需要的除数是1,1,3,1,5,3,7,1,9,5,这些除数之和是36. 所以答案=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

就像其他人已经说过的，看一下约束条件。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

这里有一个小的Python函数： https:/repl.itreplsOlivedrabKeyProjections。

Answer 2

本身这更是一个数学问题:如果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;
        }
    }
}

Answer 3

我想知道这样的东西是否就是One Lyner的意思。

(注意，这段代码中有两个错误，在注释中已经说明，也可以通过One Lyner的新代码来阐明)。

C++代码。

#include <vector>
#include <iostream>
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;
        ll k, _k, result;
        vector<ll> powers;
        cin >> n >> k;

        result = n * (n + 1) / 2;
        _k = k;

        while (_k <= n) {
            powers.push_back(_k);
            _k = _k * k;
        }

        for (ll p : powers) {
            ll num_js = n / p;
            result -= num_js * (num_js + 1) / 2 * (p - 1);
            int i = 0;
            while (p * powers[i] <= n) {
                result += powers[i] * (p - 1);
                i = i + 1;
            }
        }

        cout << result << '\n';
    }
}