作者热门文章
- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
问题如下:
给定两个数字 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';
}
}
#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';
}
}
最佳答案
就像其他人已经说过的,看看约束: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
直到总和为空...
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
关于c++ - 一个数的最大除数与质因数的关系,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61867604/
我只是写了下面的代码来利用筛法找到大于 2 的某个自然数的最大质因数。 该程序构建、运行并适用于较小的测试值,但对于大于 1000000 的值只会崩溃。 我自己写了这个——并且相信它可能会非常低效——
我是一名优秀的程序员,十分优秀!