xdu 1022（数论筛法） - c++编程基础

TOP

xdu 1022（数论筛法）

2015-11-21 01:02:54 来源: 作者: 【大中小】浏览:1次

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; }


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：leetcode-Course Schedule	下一篇：POJ 3186 Treats for the Cows

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: