QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#409956#8111. CoachesDinalWA 3ms3900kbC++141.4kb2024-05-12 23:20:122024-05-12 23:20:12

Judging History

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

  • [2024-05-12 23:20:12]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3900kb
  • [2024-05-12 23:20:12]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n,a,b;
ll solve(ll x,ll y,ll z,ll r);
ll evlos(ll x,ll y,ll z,ll r);
ll solve2(ll x,ll y,ll z,ll r){
	ll X=x,Y=y;
	x%=z,y%=z;
	if(x>=r)return x;
	if(!a)return LLONG_MAX;
	x=z-1-x,y=z-y,r=z-1-r;
	int kk=solve(x,y,z,r);
	if(kk==-1)return LLONG_MAX;
	return X+Y*kk;
	
}
void reimu_main(){
	cin>>n>>a>>b;
	ll l=a*b/__gcd(a,b);
	ll ra=n%a,rb=n%b,rl=n%l;
	ll sx=n/a+n/b-n/l*2;
	ll sy=(min(ra,rb)<rl);
	if(solve2(ra,a,b,rb)<rl)sy=2;
	if(solve2(rb,b,a,ra)<rl)sy=2;
	printf("%lld\n",n-sx+sy);
}

int main(){
	int T;cin>>T;
	while(T--)reimu_main();
	return 0;
}
//ll solve(ll x,ll y,ll z,ll r){
//	if(x<=r)return 0;
//	if(!y)return -1;
//	if(2*y>z)return evlos(z-1-x,z-y,z,z-1-r);
//	ll k1=(z-x+y-1)/y,xx=(x+y*k1)%z;
//	ll yy=(y-z%y)%y;
//	ll cs=solve(xx,yy,y,r);
//	if(cs==-1)return -1;
//	ll res=(z+y-1)/y*cs+k1-(xx+cs*yy)/a;
//	return res;
//}
ll solve(ll c,ll a,ll b,ll d){
	if(c<=d)return 0;
	if(a==0)return -1;
	if(2*a>b)return evlos(b-1-c,b-a,b,b-1-d);
	int k1=(b-c+a-1)/a,cc=(c+1ll*k1*a)%b;
	int aa=(a-b%a)%a;
	int cs=solve(cc,aa,a,d);
	if(cs==-1)return -1;
	int an=(b+a-1)/a*cs+k1-(cc+1ll*aa*cs)/a;
	return an;
}
ll evlos(ll x,ll y,ll z,ll r){
	if(x>=r)return 0;
	if(!y)return -1;
	ll k1=(r-x+y-1)/y,xx=x+y*k1;
	if(xx<z)return k1;
	ll cs=solve(xx-r,y,z,z-r-1);
	if(cs==-1)return -1;
	return cs+k1;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3780kb

input:

2
5 2 3
10 7 2

output:

3
6

result:

ok 2 number(s): "3 6"

Test #2:

score: -100
Wrong Answer
time: 3ms
memory: 3900kb

input:

1728
7 6 3
10 12 1
6 2 7
8 4 10
11 10 5
1 6 8
3 3 5
9 2 6
11 1 5
1 1 8
7 3 6
6 10 9
2 1 7
3 4 7
8 3 4
4 5 9
9 4 3
6 2 8
11 4 1
6 8 4
11 1 8
9 11 2
9 6 1
5 3 8
7 1 8
7 11 12
3 9 1
2 12 6
7 2 6
5 11 10
9 5 3
3 6 2
7 5 5
12 4 3
7 8 2
8 11 11
10 1 10
5 1 7
9 1 7
8 1 6
8 4 6
5 5 11
12 3 7
3 6 8
6 3 11
6 ...

output:

6
2
5
8
10
1
4
8
4
2
6
6
2
3
6
4
6
5
4
7
3
7
3
6
2
7
2
2
5
5
7
4
7
7
6
8
1
2
3
3
7
6
9
3
6
5
11
4
1
1
12
3
8
1
5
6
12
3
10
2
10
5
1
2
10
7
3
12
1
12
10
6
1
7
3
5
10
7
11
10
2
4
1
7
9
8
2
5
4
3
11
1
9
11
3
9
9
8
7
10
3
2
2
4
2
4
3
10
5
7
9
2
12
6
4
10
2
1
9
12
6
1
9
11
1
6
2
4
12
8
7
7
10
11
10
1
2
6...

result:

wrong answer 2nd numbers differ - expected: '1', found: '2'