199. 余数之和

Dear 丶 2021-10-29 14:26 277阅读 0赞

[![知识共享许可协议][80x15.png]][80x15.png 1]  
本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可。  
题目链接：https://www.acwing.com/problem/content/description/201/  
给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值。

例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7。  
输入格式

输入仅一行，包含两个整数n, k。  
输出格式

输出仅一行，即j(n, k)。  
数据范围

1≤n,k≤109

输入样例：

5 3

输出样例：

7

分析:  
数学题，证明一大串。代码一丢丢。我这该死的智商呀。

首先：  
k%i = k - k / i \* i。  
故：  
k%i的和 等价于 n \* k - k / i \* i;  
所以，现在的目的转换成了求k/i \* i的和了。  
我们可以一个n = 10 k = 8 为例子，更加形象的说明。  
当i等于 1 2 3 4 5 6 7 8 9 10  
此时k/i 8 4 2 2 1 1 1 1 0 0  
我们可以发现：  
有一部分的值是会连续相等的。  
我们是否可以找到每一部份相等值得开头和结尾来进行求和，从而省去许多时间呢?  
我们假设x为开头，gx为结尾。  
那么可知  
k/x == k/gx（这里两个除法，都为向下取整）。  
那么可得gx = k / (floor)(k/x);  
从而我们可以用等差序列进行求和。这也是除法分块的思想。

#include"stdio.h"
    #include"string.h"
    #include"map"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    ll n,k;
    ll sum;
    
    int main()
    {
        scanf("%lld%lld",&n,&k);
        sum = n * k;
        for(int i = 1,gx; i <= n; i = gx + 1)
        {
            gx = (k / i  ? min(k/(k/i),n) : n);
            sum -= (k / i) * (i + gx) * (gx - i + 1) / 2;
        }
        printf("%lld\n",sum);
    }

[80x15.png]: https://i.creativecommons.org/l/by-sa/4.0/80x15.png
[80x15.png 1]: http://creativecommons.org/licenses/by-sa/4.0/

发表评论取消回复

表情：

评论列表（有 0 条评论，277人围观）

还没有评论，来说两句吧...

相关阅读

相关 flowable，199boge，基础

一 Flowable介绍 1. BPMN 1. 一个软件协议，此协议用于约定了流程框架的开发规范。比如说，我们去绘制流程图的图标的规范。 2

左手的ㄟ右手/ 2023年09月24日 13:38/ 0 赞/ 64 阅读

相关 P2261-余数求和

1 include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll;

「爱情、让人受尽委屈。」/ 2023年06月01日 08:54/ 0 赞/ 8 阅读

相关 NYOJ 205 求余数

求余数时间限制： 1000 ms | 内存限制： 65535 KB 难度： 3 描述现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除1

╰半夏微凉°/ 2022年08月25日 01:50/ 0 赞/ 148 阅读

相关中国余数定理

我国古代数学名著《孙子算经》载有一道数学问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”这里的几何指多少的意思。翻译成数学语言就是：求正整数N，使

「爱情、让人受尽委屈。」/ 2022年08月13日 13:43/ 0 赞/ 273 阅读

相关 javascript 取整,取余数

1.丢弃小数部分，保留整数部分 > parseInt(5/2) > > 2 2.向上取整，有小数，则整数部分加1 > Math.ceil(5/2) > > 3 3.

Love The Way You Lie/ 2022年07月15日 15:49/ 0 赞/ 192 阅读

相关同余定理（求余数）

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数输入第一行有一个整数m(1<=m<=8),表示有m组测试数

左手的ㄟ右手/ 2022年07月15日 11:29/ 0 赞/ 211 阅读

相关同余定理（求余数）

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数输入第一行有一个整数m(1<=m<=8),表示有m组测试数

Bertha 。/ 2022年07月15日 11:29/ 0 赞/ 220 阅读

相关一个余数问题的思考

刚刚在贴吧上看到一个很简单的算法小问题，顺便看到了很多人不同的思路。我觉得很有意思，所以也来研究一下。问题如下： > 一筐鸡蛋： > 1个1个拿，正好拿完。 >

朱雀/ 2022年06月17日 12:14/ 0 赞/ 159 阅读

相关九的余数

九的余数时间限制：3000 ms | 内存限制：65535 KB 难度：3 描述现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数整除

迈不过友情╰/ 2022年06月01日 02:07/ 0 赞/ 155 阅读

相关 199. 余数之和

[![知识共享许可协议][80x15.png]][80x15.png 1] 本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可

Dear 丶/ 2021年10月29日 14:26/ 0 赞/ 278 阅读