QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#373818#2042. The BalanceKKT89100 ✓0ms3760kbC++171.2kb2024-04-02 07:49:362024-04-02 07:49:38

Judging History

你现在查看的是最新测评结果

  • [2024-04-02 07:49:38]
  • 评测
  • 测评结果:100
  • 用时:0ms
  • 内存:3760kb
  • [2024-04-02 07:49:36]
  • 提交

answer

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	ll a,b,d;
	while(cin >> a >> b >> d,a){
		int g=__gcd(__gcd(a,b),d);
		a/=g; b/=g; d/=g;
		pair<ll,ll> res;
		res=make_pair(1e9,1e9);
		ll sum=res.first+res.second;
		ll ans=res.first*a+res.second*b;
		for(ll x=0;x<=50000;x++){
			if(sum<=x)break;

			if((a*x-d)%b==0){ 
				ll y=abs((a*x-d)/b);
				if((sum>x+y)||(sum==x+y&&ans>x*a+b*y)){
					sum=x+y;
					res=make_pair(x,y);
					ans=res.first*a+res.second*b;
				}
			}
			if((a*x+d)%b==0){
				ll y=abs((a*x+d)/b);
				if((sum>x+y)||(sum==x+y&&ans>x*a+b*y)){
					sum=x+y;
					res=make_pair(x,y);
					ans=res.first*a+res.second*b;
				}
			}
		}
		printf("%lld %lld\n",res.first,res.second);
	}
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3760kb

input:

1 2 50000
9999 10000 1
58 14 5762
1620 5418 3240
3027 9259 26491
3349 4530 6564
3759 479 1355
6259 6201 15544
1141 4904 45837
1137 7358 3311
6656 907 26450
7114 3129 558
1 4733 35498
3491 151 2265
1147 3389 27770
360 5506 47160
3020 4061 7176
7268 510 23100
5416 922 1156
382 4803 2284
1637 1600 1352...

output:

0 25000
1 1
95 18
2 0
2059 676
1686 1245
12 97
268 268
871 212
1149 178
422 3126
1191 2708
2367 7
0 15
429 137
131 0
707 524
45 596
149 874
2068 164
629 652
25 860
540 248
420 1782
325 34
10 0
291 1395
99 98
272 680
2229 354
167 1633
785 59
211 27
625 170
1585 999
1305 1555
638 15
461 827
2288 780
4...

result:

ok 100 lines