首页 > 其他分享 >Educational Codeforces Round 5-E. Sum of Remainders

Educational Codeforces Round 5-E. Sum of Remainders

时间:2023-06-12 17:32:55浏览次数:61  
标签:Educational Remainders ll cnt Codeforces ans input MOD mod


原题链接


E. Sum of Remainders



time limit per test



memory limit per test



input



output



Calculate the value of the sum: n mod 1 + n mod 2 + n mod 3 + ... + n mod m. As the result can be very large, you should print the value modulo 109 (the remainder when divided by 109).

The modulo operator a mod b stands for the remainder after dividing a by b. For example 10 mod 3 = 1.



Input



The only line contains two integers n, m (1 ≤ n, m ≤ 1013) — the parameters of the sum.



Output



Print integer s — the value of the required sum modulo 109.



Examples



input



3 4



output



4



input



4 4



output



1



input



1 1



output



0






这道题分三步来做:

1.当m > n时 ans += n * (m - n); m = n - 1;

2.当m < n && m > 1e6时,分块取模,比如 m > n / 2那么(n / 2, m]的取模为等差数列求和 = (n % (n/2+1) + n % m) * (m - n + 1)/ 2; m = n / 2;以此类推

3.当 m <= 1e6时for(i = 2; i <= m; i++) ans += n % i;


#include <bits/stdc++.h>
#define maxn 200005
#define MOD 1000000007
using namespace std;
typedef long long ll;

int main(){
	
//	freopen("in.txt", "r", stdin);
	ll n, m, ans = 0;
	
	scanf("%I64d%I64d", &n, &m);
    if(m > n){
    	ans += (m - n) % MOD * (n % MOD) % MOD; 
    }
    m = min(n - 1, m);
    int cnt = 2;
    
    while(m > 1000000){
    	ll d = n / cnt + 1;
    	if(m >= d){
    		ll p1 = n % d;
    		ll p2 = n % m;
    		ans += (p1 + p2) % MOD * ((m - d + 1) % MOD) % MOD * 500000004 % MOD;//2 * 500000004 % MOD == 1
    		ans %= MOD;
    		if(n % cnt == 0)
    		 m = n / cnt - 1;
    		else
    		 m = n / cnt;
		}
		cnt++;
	}
	for(int i = 2; i <= m; i++){
		ans += n % i;
		ans %= MOD;
	}
	cout << ans << endl;
	
	return 0;
}




标签:Educational,Remainders,ll,cnt,Codeforces,ans,input,MOD,mod
From: https://blog.51cto.com/u_16158872/6464282

相关文章

  • Codeforces Round #346 (Div. 2)-E. New Reform
    原题链接E.NewReformtimelimitpertestmemorylimitpertestinputoutputn citiesconnectedby m bidirectionalroads.Noroadconnectsacitytoitself,andeachpairofcitiesisconnectedbynomorethan......
  • Codeforces Round #291 (Div. 2)-D. R2D2 and Droid Army(RMQ)
    原题链接D.R2D2andDroidArmytimelimitpertestmemorylimitpertestinputoutputAnarmyof n droidsislinedupinonerow.Eachdroidisdescribedby m integers a......
  • Codeforces Beta Round #22 (Div. 2 Only)-D. Segments
    原题链接D.SegmentstimelimitpertestmemorylimitpertestinputoutputYouaregiven nInputThefirstlineoftheinputcontainssingleintegernumber n (1 ≤ n ......
  • Codeforces Round #190 (Div. 2)-C. Ciel and Robot
    原题链接C.CielandRobottimelimitpertestmemorylimitpertestinputoutputs.Eachcharacterof sU':goup,(x,y)  → D':godown,(x,y)  → L':goleft,(x,y)  → R':goright,(x,y) ......
  • Codeforces Round #362 (Div. 2)-D. Puzzles
    原题链接D.PuzzlestimelimitpertestmemorylimitpertestinputoutputBarneylivesincountryUSC(UnitedStatesofCharzeh).USChas n citiesnumberedfrom 1 through......
  • Codeforces Beta Round #29 (Div. 2, Codeforces format)-D. Ant on the Tree
    原题链接D.AntontheTreetimelimitpertestmemorylimitpertestinputoutputConnectedundirectedgraphwithoutcyclesiscalledatree.Treesisaclassofgraphswhic......
  • CodeForces 4B Before an Exam(DP)
    思路:令dp[i][j]为做了i天用了j时间,然后随便转移一下就可以了#include<cstdio>#include<queue>#include<cstring>#include<iostream>#include<cstdlib>#include<algorithm>#include<vector>#include<map>#include<string>#......
  • CodeForces 4D Mysterious Present(DP)
    题意:你有一张长宽为x,y的卡片同时有n个盒子,长宽分别为xi,yi。然后问你卡片最多塞多少层盒子并且把这些盒子按照从里到外输出。思路:由于数据给小了,所以n^2的DP也是可以水过的~#include<iostream>#include<cstdio>usingnamespacestd;constintmaxn=5005;intx[maxn],y[maxn]......
  • CodeForces 645A Amity Assessment
    题意:给你一个2X2的华容道你,问能不能通过初始给出的棋盘然后变换到最后的棋盘思路:由于是一个2X2的...所以怎么做都可以..留意到每个棋子的移动其实都是顺时针或者逆时针的就好做了。#include<cstdio>#include<queue>#include<cstring>#include<iostream>#include<cstdlib>......
  • Codeforces Round 877 (Div. 2)
    Preface补题这场补题的时候直接成腐乳了,A题挂两发,B题挂两发,C题挂一发是真的抽象虽然D是个套路题看一眼就秒了,但如果真的比赛时候打真要罚时爆炸了的说后面的EF还是做不来啊岂可修,不过都很有启发性让人感觉神清气爽,不像傻逼蓝桥杯花钱买罪受A.BlackboardList刚开始想错方......