程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> NYOJ 508 余數求和 (數論問題)

NYOJ 508 余數求和 (數論問題)

編輯：關於C++

題目描述

給你兩個數n，k，請求出 border=0 的值。

輸入每行兩個數n, k(1 <= n, k <= 10^9).輸出輸出和，每個結果占一行。樣例輸入

5 4
5 3

樣例輸出

5
7

題目分析:

對於此題不能直接進行暴力，數值大，只能用sqrt(n)的算法，首先計算n%i的余數和，i=1~n；注意到：n%i=n/i*i;

因此我們可以模擬從i=1~sqrt(n);sum+=n%i;對於i對應的j=n/i，可以知道(n/i~n/i+1)==d；對與這組數，計算得到

s1=((n/i-n/(i+1))*n)-d*(n/(i+1)+1+......+n/i)；sum+=s1;直到循環結束，就得到n%i的余數和，我們用ModSum(n)。

現在我們求k%i的余數和，i=1~n；進行分析k和n即可，

一、kk時，k%n==k

二、k=n res=ModSum(k)

三、k>n res=ModSum(k); { for(int i=n+1;i<=n;i++)

res-=k%i;//減去多計算的值即可。

}

AC代碼：

 
/**
 *1、ModSum1()：O(n)
 *2、ModSum2()：O(sqrt(n))
 *1   2   3   4
 *16  8   5   4
 *  1   2   3
 */
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define MOD 1000000007
using namespace std;
LL ModSum1(LL n){
    LL t=(n+1)/2-1;
    LL sum=t*(t+1)/2;
    for(LL i=1;i<=n/2;i++){
        sum+=n-(n/i*i);
    }
    return sum;
}

LL ModSum2(LL n,LL k){
    LL sum=0,n1=n;
    n=k;
    LL tem=sqrt(n);
    for(LL i=1;i<=tem;i++){
        if(n/i==i){
            sum+=n-n/i*i;
            continue;
        }
        sum+=n-n/i*i;
        sum=sum;
        //cout<>n>>k){
        //LL sum1=ModSum1(n);
        LL sum2;

        sum2=ModSum2(n,k);


        cout<