QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#582624#9376. GameSwd146296#WA 195ms3632kbC++14863b2024-09-22 17:01:202024-09-22 17:01:20

Judging History

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

  • [2024-09-22 17:01:20]
  • 评测
  • 测评结果:WA
  • 用时:195ms
  • 内存:3632kb
  • [2024-09-22 17:01:20]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mod=998244353ll;
int _;
int x,y,a,b,d,sub,sinv;
ll ksm(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}
ll norm(ll x){
	return ((x%mod)+mod)%mod;
}
ll solve(int x,int y){
	if(x==y)return a*sinv%mod;//turansiwang
	if(x<y){//bunengshu
		int times=y/x;
		if(y==x*times)times-=1;
		int newy=y-x*times;
		ll bushu=ksm(a*sinv%mod,times);
		return solve(x,newy)*bushu%mod;
	}
	if(x>y){//zhiyao yingyiba
		int times=x/y;
		if(x==y*times)times-=1;
		int newx=x-y*times;
		ll ying=norm(1-ksm(b*sinv%mod,times));
		return norm(ying+norm(1-ying)*solve(newx,y)%mod);
	}
}
int main(){
	cin>>_;
	while(_--){
		cin>>x>>y;
		cin>>a>>b>>sub;
		sub=a+b;
		sinv=ksm(sub,mod-2);
		cout<<solve(x,y)<<endl;
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

3
1 1
2 2 6
1 3
2 3 6
3 4
7 3 15

output:

499122177
910398850
220911476

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 195ms
memory: 3632kb

input:

100000
1 1000000000
12980050 128257807 266126484
1 1000000000
400255084 123438563 768881284
1000000000 1000000000
24563487 72082135 450057094
1 1000000000
56952077 40876000 193815114
1000000000 1000000000
82048274 239365585 326520865
1000000000 1
309821265 346013425 963168258
1 1
104158269 199365020...

output:

23409871
109354877
683273820
241464537
-642876456
603651894
866111085
-27984652
252811383
31644570
891062361
942959651
-433710537
-265382174
802636063
278805887
-69267389
346523045
-41028232
170484524
73605878
55001858
-544733033
602843698
851970839
760828265
659400395
182568424
-553127905
930884311...

result:

wrong answer 1st lines differ - expected: '947058399', found: '23409871'