QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#581883#9376. GamecbbdhzML 0ms3648kbC++20886b2024-09-22 14:30:102024-09-22 14:30:11

Judging History

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

  • [2024-09-22 14:30:11]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:3648kb
  • [2024-09-22 14:30:10]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
int qp(int a, int b, int mod)
{
	int ans = 1;
	while (b)
	{
		if (b & 1)
		{
			ans = ans * a % mod;
		}
		b >>= 1;
		a = a * a % mod;
	}
	return ans;
}
int temp;
int dfs(int x, int y, int p1, int p2)
{
	if (y == 0)
	{
		return 1;
	}else
	if (x == y)
	{
		return p1 * temp % mod;
	}
	else if(x>y){
		return (p1*temp%mod+p2 * temp % mod *dfs(x - y, y, p1, p2)%mod)%mod;
	}
	else if (x < y)//少
	{
		int t = y / x;
		if (y % x == 0)
		{
			t--;
		}
		return qp(p1 * temp % mod, t, mod) * dfs(x, y - t * x, p1, p2) % mod;
	}
}
void solve()
{
	int x, y; cin >> x >> y;
	int a, b, c; cin >> a >> b >> c;
	temp = qp(a + b, mod - 2, mod);
	cout << dfs(x, y, a, b) << endl;
}
signed main()
{
	int T; cin >> T;
	while (T--)
	{
		solve();
	}

}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Memory Limit Exceeded

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:

947058399
376449942
612621163
138416357
592200562

result: