专栏首页小樱的经验随笔BZOJ 1257: [CQOI2007]余数之和sum【神奇的做法,思维题】

BZOJ 1257: [CQOI2007]余数之和sum【神奇的做法,思维题】

1257: [CQOI2007]余数之和sum

Time Limit: 5 Sec  Memory Limit: 162 MB

Submit: 4474  Solved: 2083

[Submit][Status][Discuss]

Description

给出正整数n和k,计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

Input

输入仅一行,包含两个整数n, k。

Output

输出仅一行,即j(n, k)。

Sample Input

5 3

Sample Output

7

HINT

50%的数据满足:1<=n, k<=1000 100%的数据满足:1<=n ,k<=10^9

Source

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1257

分析:用了一个看起来比较奇怪的方法,首先x % i = x – (int)(x / i) * i,这个很好YY吧 然后可以找出每个(int)(x / i)相等的一段用等差数列求和来做。可以证明最多分成sqrt(n)段。

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 inline int read()
 5 {
 6     int x=0,f=1;
 7     char ch=getchar();
 8     while(ch<'0'||ch>'9')
 9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 int n,k;
22 ll ans;
23 int main()
24 {
25     n=read();
26     k=read();
27     if(n>k)
28     {
29         ans=(ll)(n-k)*k;
30         n=k;
31     }
32     int r;
33     for(int i=1;i<=n;i=r+1)
34     {
35         int t=k/i;
36         r=k/t;
37         if(r>=n)r=n;
38         ans+=(ll)(r-i+1)*k-(ll)(r-i+1)*(i+r)/2*t;
39     }
40     printf("%lld\n",ans);
41     return 0;
42 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 冒泡排序简单操作模版及实例分析

    1 #include <bits/stdc++.h> 2 using namespace std; 3 inline int read() 4 { 5...

    Angel_Kitty
  • 51Nod 1632 B君的连通(递归,快速幂)

    1632 B君的连通 基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题 B国拥有n个城市,其交通系统呈树状结构,即任意两个城市...

    Angel_Kitty
  • BZOJ 1800: [Ahoi2009]fly 飞行棋【思维题,n^4大暴力】

    1800: [Ahoi2009]fly 飞行棋 Time Limit: 10 Sec  Memory Limit: 64 MB Submit: 1689  So...

    Angel_Kitty
  • 清北集训Day6T1(生成函数)

    听rqy说可以用生成函数做,感觉比较有意思 我们考虑在DP转移的时候, $5,7,9$这三个数是没有限制的 因此他们出现的次数用01串表示的话就是$111111...

    attack
  • 【CodeForces 672B】Different is Good

    因为只能是26个字母,显然大于26的不可能有答案,其它情况ans+=u[i]-1;u[i]是字母出现的次数。

    饶文津
  • BZOJ1008: [HNOI2008]越狱(组合数)

    监狱有连续编号为 1…N1…N 的 NN 个房间,每个房间关押一个犯人,有 MM 种宗教,每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同,就可能发生越狱...

    attack
  • 洛谷P3773 [CTSC2017]吉夫特(Lucas定理,dp)

    满足$b_1 < b_2 < \dots < b_k$且$a_{b_1} \geqslant a_{b_2} \geqslant \dots \geqslant...

    attack
  • POJ3734 Blocks(生成函数)

    任意的是\(e^x\),偶数的是\(\frac{e^x + e^{-x}}{2}\)

    attack
  • 18:鸡尾酒疗法

    18:鸡尾酒疗法 总时间限制: 1000ms 内存限制: 65536kB描述 鸡尾酒疗法,原指“高效抗逆转录病毒治疗”(HAART),由美籍华裔科学家何大一于...

    attack
  • jenkins 邮件发送错误

    本文转载自:https://blog.ossez.com/archives/3096

    HoneyMoose

扫码关注云+社区

领取腾讯云代金券