程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> xdu 1022(數論篩法)

xdu 1022(數論篩法)

編輯:關於C++

 

1022: A simple math problem 2

時間限制: 1 Sec 內存限制: 128 MB
提交: 73 解決: 13
[提交][狀態][討論版]

題目描述

高斯函數: [x]表示,小於等於x的最大整數,即向下取整。 如 [2.5]=2,[1.2]=1等。 定義函數f(n)=[n/1]+[n/2]+[n/3]+...+[n/n] . sum(a,b)=f(a)+f(a+1)+...+f(b) 給定a,b,求sum(a,b)

輸入

多組輸入(不超過10000組) 每行輸入 a,b,其中1<=a<=b<=1000000

輸出

多組輸出 每行輸出sum(a,b)%1007,並換行

樣例輸入

1 1
1 2

樣例輸出

1
4

提示

 

 

 

來源


 

令f(n)的含義實際上是有多少對(a,b)滿足a*b<=n(自己沒想到,在叉姐指導下才弄明白,感謝),那麼我們可以領g(n)表示有多少對(a,b)滿足a*b=n,然後對g求個前綴和f(n)就出來了。

 

 

#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const ll mod = 1007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define pb push_back
ll f[maxn];
void init(int n)
{
    memset(f,0,sizeof f);
    for(int i = 1; i <= n; i++)
        for(int j = i; j <= n; j += i)
            f[j]++;
    for(int j = 1; j <= n; j++) {
        f[j] = (f[j]+f[j-1])%mod;
    }
    for(int j = 1; j <= n; j++) {
        f[j] = (f[j]+f[j-1])%mod;
    }
}
int main()
{
    init(1000000);
    int L,R;
    while(~scanf("%d%d",&L,&R)) {
        printf("%d\n", (f[R]-f[L-1]+mod)%mod);
    }
    return 0;
}


 

 

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