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

110ms水过

Posted by astoninfer at 2015-05-29 23:44:25 on Problem 2800
找规律的过程还是比较费神的,注意到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