程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> NYOJ 508 余數求和 (數論問題)

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

編輯:C++入門知識

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


題目描述

 

給你兩個數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<

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved