问题描述
如果我们有2个数字,说 a和b
那么,我们如何才能找到的B%总和其中i从1范围值到
?一种方式是通过从1所有的值迭代到但没有任何有效的方法?(为O更好的(N)?)如:如果一个= 4和b = 5则需要ANS = 5%1 + 5%2 + 5%3 + 5%4 = 4谢谢你。
if we have 2 numbers, say a and b
then how can we find the value of sum of b%i where i ranges from 1 to a
?One way is to iterate through all values from 1 to a but is there any efficient method?(better than O(n) ?)E.g : if a = 4 and b = 5 then required ans = 5%1+5%2+5%3+5%4=4Thanks.
推荐答案
有关 I> b
,我们 B%我== b
,使之和的那部分很容易计算在固定时间内( (AB)* B
,如果 A> = B
,否则为0)
For i > b
, we have b % i == b
, so that part of the sum is easily calculated in constant time ((a-b)*b
, if a >= b
, 0 otherwise).
部分的 I< = B
还有待计算(我== b
给出0,从而可以忽略)。你可以这样做,在O(开方(B))步骤,
The part for i <= b
remains to be calculated (i == b
gives 0, thus may be ignored). You can do that in O(sqrt(b)) steps,
- 为
I&LT; =开方(B)
,计算B%I
并添加总结李> - 为
I&GT;开方(B)
,让K =楼(B / I)
,然后B%I = = b - K * I
和K&LT;开方(B)
。因此,对于K = 1
到上限(开方(B)) - 1
,让喜=楼(B / K)
和LO =楼(B /(K + 1))
。有喜 - 罗
号我
,使得K * I&LT; = B&LT; (K + 1)* I
的B%I
对他们来说是sum_ {LO&LT的总和; I&LT; =喜}(B - K * I)=(HI - LO)* B - K *(HI-LO)*(HI + LO + 1)/ 2
李。 >
- For
i <= sqrt(b)
, calculateb % i
and add to sum - For
i > sqrt(b)
, letk = floor(b/i)
, thenb % i == b - k*i
, andk < sqrt(b)
. So fork = 1
toceiling(sqrt(b))-1
, lethi = floor(b/k)
andlo = floor(b/(k+1))
. There arehi - lo
numbersi
such thatk*i <= b < (k+1)*i
, the sum ofb % i
for them issum_{ lo < i <= hi } (b - k*i) = (hi - lo)*b - k*(hi-lo)*(hi+lo+1)/2
.
如果 A&LT; =开方(B)
,只有第一颗子弹适用,停在 A
。如果的sqrt(B)&LT; A&LT; b
,在第二点,从 K =楼(B / A)
运行上限(开方(二) )-1
键,调整为最小 K
上限 A
。
If a <= sqrt(b)
, only the first bullet applies, stopping at a
. If sqrt(b) < a < b
, in the second bullet, run from k = floor(b/a)
to ceiling(sqrt(b))-1
and adjust the upper limit for the smallest k
to a
.
整体复杂度为O(分(A,开方(B)))。
Overall complexity O(min(a,sqrt(b))).
code(C):
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
unsigned long long usqrt(unsigned long long n);
unsigned long long modSum(unsigned long long a, unsigned long long b);
int main(int argc, char *argv[]){
unsigned long long a, b;
b = (argc > 1) ? strtoull(argv[argc-1],NULL,0) : 10000;
a = (argc > 2) ? strtoull(argv[1],NULL,0) : b;
printf("Sum of moduli %llu %% i for 1 <= i <= %llu: %llu\n",b,a,modSum(a,b));
return EXIT_SUCCESS;
}
unsigned long long usqrt(unsigned long long n){
unsigned long long r = (unsigned long long)sqrt(n);
while(r*r > n) --r;
while(r*(r+2) < n) ++r;
return r;
}
unsigned long long modSum(unsigned long long a, unsigned long long b){
if (a < 2 || b == 0){
return 0;
}
unsigned long long sum = 0, i, l, u, r = usqrt(b);
if (b < a){
sum += (a-b)*b;
}
u = (a < r) ? a : r;
for(i = 2; i <= u; ++i){
sum += b%i;
}
if (r < a){
u = (a < b) ? a : (b-1);
i = b/u;
l = b/(i+1);
do{
sum += (u-l)*b;
sum -= i*(u-l)*(u+l+1)/2;
++i;
u = l;
l = b/(i+1);
}while(u > r);
}
return sum;
}
这篇关于发现的范围内模运算的总和的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!