QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#510457#9158. 分数ninjadoggy1234#50 111ms18268kbC++204.5kb2024-08-09 05:08:292024-08-09 05:08:30

Judging History

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

  • [2024-08-09 05:08:30]
  • 评测
  • 测评结果:50
  • 用时:111ms
  • 内存:18268kb
  • [2024-08-09 05:08:29]
  • 提交

answer

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <cstring>

#include <algorithm>
#include <chrono>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_set>
#include <sstream>
#include <string>
#include <map>
#include <unordered_map>
#include <vector>
#include <functional>
#include <numeric>

#define int long long
#define FOR(a,b) for(int a = 0; a < b; a++)
#define All(vec) vec.begin(),vec.end()

using std::string;
using std::vector;
using std::pair;
using std::cin;
using std::cout;
const int oo = 3074457345618258602LL;

std::stringstream out;

template<class T> bool ckmax(T& a, const T& b) {
	return a < b ? a = b, 1 : 0;
}
template<class T> bool ckmin(T& a, const T& b) {
	return a > b ? a = b, 1 : 0;
}

template<int D, typename T>
struct Vec : public vector<Vec<D - 1, T>> {
	static_assert(D >= 1, "Vector dimension must be greater than zero!");
	template<typename U, typename... Args>
	Vec(U n = U(), Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
	}
	template<typename... Args>
	Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) {
	}
};
template<typename T>
struct Vec<1, T> : public vector<T> {
	template<typename... Args>
	Vec(Args... args) : vector<T>(args...) {
	}
	Vec(int n = 0, const T& val = T()) : vector<T>(n, val) {
	}
};

const bool kReadTestCases = 0;
const bool kLocalRun = 0;
const bool kBruteSolve = 0;
struct Fraction {
	int num, denom;


};
struct Solution {

	void ReadInput() {
	}

	void Solve(std::stringstream& out) {


		int N, M;
		cin >> N >> M;
		int bound = std::max(N, M) + 1;
		std::set<pair<int, int>> vis;
		int ans = 0;
		std::function<void(int, int)> DFS = [&](int n, int d) {
			if (n >= bound || d >= bound)return;
			if (d <= 0 || n <= 0)return;
			if (n * 2 > d && n < 2 * d) {
				return;
			}
			int gcd = std::gcd(n, d);
			n /= gcd;
			d /= gcd;
			if (!vis.emplace(n, d).second) {
				return;
			}
			if (n <= N && d <= M) {
				ans++;
			}
			DFS(d, n);
			DFS(n + 2 * d, d);
			DFS(n - 2 * d, d);

			};
		DFS(1, 2);
		out << ans << "\n";
		//int x = 1000;
		//for (int i = 1; i <= x; i++) {
		//	int gcd = std::gcd(i, x);
		//	int N, M;
		//	cin >> N >> M;
		//	if (gcd == 1) {
		//		cout << i << "\n";
		//	}
		//}
		//int bound = std::max(N, M) + 1;
		//Vec<2, int> dp(bound, bound, -1);
		//std::function<int(int, int)> Solve = [&](int n, int d) {
		//	int& ans = dp[n][d];
		//	if (n == 0) {
		//		ans = 1;
		//	} else if (n * 2 > d && n < 2 * d) {
		//		ans = 0;
		//	} else if (ans == -1) {
		//		if (n > d) {
		//			ans = Solve(n - 2 * d, d);
		//		} else {
		//			ans = Solve(d, n);
		//		}
		//	}
		//	return ans;
		//	};
		//int ans = 0;
		//for (int i = 1; i <= N; i++) {
		//	for (int j = 1; j <= M; j++) {
		//		if (std::gcd(i, j) == 1) {
		//			ans += Solve(i, j);
		//		}
		//	}
		//}
		//out << ans << "\n";
	}

	void SolveBrute(std::stringstream& out) {

	}
	void GenInput() {

	}
	void PrintInput() {

	}

	inline vector<int> ReadVec(int N) {
		vector<int> vec(N);
		FOR(i, N) {
			cin >> vec[i];
		}
		return vec;
	}

	inline string Stringify(vector<int>& arr) {
		std::stringstream ss;
		FOR(i, arr.size()) {
			ss << arr[i] << " \n"[i == arr.size() - 1];
		}
		return ss.str();
	}
};


void RunLocal() {
	srand(time(NULL));
	int iter = 0;
	while (true) {
		if (++iter % 1000 == 0) {
			std::cout << iter << "\n";
		}
		Solution solution;
		solution.GenInput();
		std::stringstream ss1;
		std::stringstream ss2;
		solution.Solve(ss1);
		solution.SolveBrute(ss2);
		string ans = ss1.str();
		string ans_correct = ss2.str();
		if (ans != ans_correct) {
			solution.PrintInput();
			cout << "\n\n";
			cout << "Wrong answer:\n";
			cout << "---------------------------------------------------------\n";
			cout << ans << "\n";
			cout << "Correct answer:\n";
			cout << "---------------------------------------------------------\n";
			cout << ans_correct << "\n";
			break;
		}
	}
}

int32_t main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	if (kLocalRun) {
		RunLocal();
		return 0;
	}
	int tc = 1;
	if (kReadTestCases)std::cin >> tc;
	for (int _ = 1; _ <= tc; _++) {
		Solution solution;
		solution.ReadInput();
		if (kBruteSolve) {
			solution.SolveBrute(out);
		} else {
			solution.Solve(out);
		}
	}
	std::cout << out.str();
	std::cout.flush();
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests

Pretest #1:

score: 5
Accepted
time: 1ms
memory: 3852kb

input:

99 99

output:

406

result:

ok 1 number(s): "406"

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 3752kb

input:

98 97

output:

405

result:

ok 1 number(s): "405"

Pretest #3:

score: 5
Accepted
time: 0ms
memory: 3688kb

input:

99 96

output:

396

result:

ok 1 number(s): "396"

Pretest #4:

score: 5
Accepted
time: 0ms
memory: 4376kb

input:

995 977

output:

11153

result:

ok 1 number(s): "11153"

Pretest #5:

score: 5
Accepted
time: 4ms
memory: 4580kb

input:

991 990

output:

11220

result:

ok 1 number(s): "11220"

Pretest #6:

score: 5
Accepted
time: 4ms
memory: 4660kb

input:

976 968

output:

10900

result:

ok 1 number(s): "10900"

Pretest #7:

score: 5
Accepted
time: 104ms
memory: 17908kb

input:

7602 7864

output:

215706

result:

ok 1 number(s): "215706"

Pretest #8:

score: 5
Accepted
time: 109ms
memory: 18268kb

input:

7959 7735

output:

220256

result:

ok 1 number(s): "220256"

Pretest #9:

score: 5
Accepted
time: 108ms
memory: 17984kb

input:

7878 7863

output:

221162

result:

ok 1 number(s): "221162"

Pretest #10:

score: 5
Accepted
time: 101ms
memory: 17764kb

input:

7788 7658

output:

215323

result:

ok 1 number(s): "215323"

Pretest #11:

score: 0
Time Limit Exceeded

input:

95399 99767

output:


result:


Pretest #12:

score: 0
Time Limit Exceeded

input:

98051 99642

output:


result:


Pretest #13:

score: 0
Time Limit Exceeded

input:

95624 96007

output:


result:


Pretest #14:

score: 0
Time Limit Exceeded

input:

99208 98047

output:


result:


Pretest #15:

score: 0
Time Limit Exceeded

input:

997417 967722

output:


result:


Pretest #16:

score: 0
Time Limit Exceeded

input:

987807 956529

output:


result:


Pretest #17:

score: 0
Time Limit Exceeded

input:

971654 984345

output:


result:


Pretest #18:

score: 0
Time Limit Exceeded

input:

7892259 7983727

output:


result:


Pretest #19:

score: 0
Time Limit Exceeded

input:

7937869 29796968

output:


result:


Pretest #20:

score: 0
Time Limit Exceeded

input:

29717543 29510173

output:


result:



Final Tests

Test #1:

score: 5
Accepted
time: 1ms
memory: 3912kb

input:

96 98

output:

396

result:

ok 1 number(s): "396"

Test #2:

score: 5
Accepted
time: 1ms
memory: 3920kb

input:

100 99

output:

408

result:

ok 1 number(s): "408"

Test #3:

score: 5
Accepted
time: 1ms
memory: 3920kb

input:

99 99

output:

406

result:

ok 1 number(s): "406"

Test #4:

score: 5
Accepted
time: 4ms
memory: 4288kb

input:

963 951

output:

10634

result:

ok 1 number(s): "10634"

Test #5:

score: 5
Accepted
time: 4ms
memory: 4560kb

input:

958 974

output:

10795

result:

ok 1 number(s): "10795"

Test #6:

score: 5
Accepted
time: 4ms
memory: 4484kb

input:

966 990

output:

11003

result:

ok 1 number(s): "11003"

Test #7:

score: 5
Accepted
time: 107ms
memory: 18216kb

input:

7958 7947

output:

224482

result:

ok 1 number(s): "224482"

Test #8:

score: 5
Accepted
time: 111ms
memory: 17744kb

input:

7623 7730

output:

213444

result:

ok 1 number(s): "213444"

Test #9:

score: 5
Accepted
time: 109ms
memory: 18060kb

input:

7845 7783

output:

218916

result:

ok 1 number(s): "218916"

Test #10:

score: 5
Accepted
time: 107ms
memory: 18004kb

input:

7881 7773

output:

219451

result:

ok 1 number(s): "219451"

Test #11:

score: 0
Time Limit Exceeded

input:

99414 98698

output:


result:


Test #12:

score: 0
Time Limit Exceeded

input:

98249 96148

output:


result:


Test #13:

score: 0
Time Limit Exceeded

input:

99003 96832

output:


result:


Test #14:

score: 0
Time Limit Exceeded

input:

98266 96030

output:


result:


Test #15:

score: 0
Time Limit Exceeded

input:

968207 958885

output:


result:


Test #16:

score: 0
Time Limit Exceeded

input:

959846 998397

output:


result:


Test #17:

score: 0
Time Limit Exceeded

input:

965821 972280

output:


result:


Test #18:

score: 0
Time Limit Exceeded

input:

7855098 7962479

output:


result:


Test #19:

score: 0
Time Limit Exceeded

input:

7841076 29648718

output:


result:


Test #20:

score: 0
Time Limit Exceeded

input:

29365129 29012208

output:


result: