Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:110ms水过

Posted by shishuaicheng at 2025-10-14 20:32:42 on Problem 2800
In Reply To:110ms水过 Posted by:astoninfer at 2015-05-29 23:44:25
> 找规律的过程还是比较费神的,注意到k % i(i : 1→n)有分段等差数列即可,
> 另,数据在int边缘,不仅最终输出要用int64或longlong,中间过程只用int也会溢出
> #include <cstdio>
> 
> using namespace std;
> 
> int main(){
> 	__int64 k, n;
> 	while(~scanf("%I64d%I64d", &n, &k)){
> 		__int64 x = 0;
> 		for(int i = 1; i <= n; i++)	x += k % i;
> 		printf("check : %I64d\n", x);
> 		__int64 ans = 0;
> 		if(n > k)	 { ans = (n - k) * k; n = k; }
> 		__int64 p;
> 		for(int i = 1; ; i++)	 if(k / i <= k / ( i + 1) + 2)	{ p = i; break; }
> 		if(n <= k / (p + 1)){
> 			for(int i = 1; i <= n; i++)    ans += k % i;
> 			printf("%I64d\n", ans);
> 			continue;
> 		}
> 		for(int i = p; i >= 1; i--){
> 			int cnt = k / i - k / (i + 1);
> 			int t = k % (k / i) + (cnt - 1) * i;
> 			if(n < k / (i + 1) + 1)	break;
> 			if(n < k / i)    cnt = n - k / (i + 1);
> 			ans += cnt * (2 * t + (1 - cnt) * i) / 2;
> 		}
> 		for(int i = 1; i <= k / (1 + p); i++)	ans += k % i;
> 		printf("%I64d\n", ans);
> 	}
> 	return 0;
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator