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

Question

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

我解决这个问题的方法是：对于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';
 }

 }

有人能帮助我哪里做错了，或者建议我一些更快的逻辑来做这个问题，因为我的一些测试案例显示超过了时间限制

在查看了所有可能的解释之后，我修改了我的代码，如下所示:

#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个测试用例的时间限制超过。有人请帮忙。

Answer 1

我想知道这样的事情是否是一个莱纳的意思。

(注意，这段代码有两个错误，在评论中有描述，也可以用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';
    }
}

Answer 2

这本身更像是一个数学问题:如果cur = [1..n]，正如你已经注意到的，最大除数= dmax = cur是，如果cur % k！= 0，否则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

就像其他人已经说过的，看看约束：t=3*10^5,1

如果您的测试具有通过循环计算总和的复杂度O（n），您最终将执行t*n~10^14。那太多了。

这是一个数学挑战。您需要使用两个事实：

< li >正如您已经看到的，如果< code>i = j * k^s与< code>j%k！= 0，最大除数为< code > 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