QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#510461#9158. 分数ninjadoggy12340 0ms0kbC++204.5kb2024-08-09 05:12:132024-08-09 05:12:13

Judging History

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

  • [2024-08-09 05:12:13]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-08-09 05:12:13]
  • 提交

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;
		int ans = 0;
		std::function<void(int, int, bool)> DFS = [&](int n, int d, bool done) {
			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 (n <= N && d <= M) {
				ans++;
			}
			if (!done) {
				DFS(d, n, 1);
			}
			DFS(n + 2 * d, d, 0);
			DFS(n - 2 * d, d, 0);

			};
		DFS(1, 2, 0);
		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: 0
Memory Limit Exceeded

input:

99 99

output:


result:


Pretest #2:

score: 0
Memory Limit Exceeded

input:

98 97

output:


result:


Pretest #3:

score: 0
Memory Limit Exceeded

input:

99 96

output:


result:


Pretest #4:

score: 0
Memory Limit Exceeded

input:

995 977

output:


result:


Pretest #5:

score: 0
Memory Limit Exceeded

input:

991 990

output:


result:


Pretest #6:

score: 0
Memory Limit Exceeded

input:

976 968

output:


result:


Pretest #7:

score: 0
Memory Limit Exceeded

input:

7602 7864

output:


result:


Pretest #8:

score: 0
Memory Limit Exceeded

input:

7959 7735

output:


result:


Pretest #9:

score: 0
Memory Limit Exceeded

input:

7878 7863

output:


result:


Pretest #10:

score: 0
Memory Limit Exceeded

input:

7788 7658

output:


result:


Pretest #11:

score: 0
Memory Limit Exceeded

input:

95399 99767

output:


result:


Pretest #12:

score: 0
Memory Limit Exceeded

input:

98051 99642

output:


result:


Pretest #13:

score: 0
Memory Limit Exceeded

input:

95624 96007

output:


result:


Pretest #14:

score: 0
Memory Limit Exceeded

input:

99208 98047

output:


result:


Pretest #15:

score: 0
Memory Limit Exceeded

input:

997417 967722

output:


result:


Pretest #16:

score: 0
Memory Limit Exceeded

input:

987807 956529

output:


result:


Pretest #17:

score: 0
Memory Limit Exceeded

input:

971654 984345

output:


result:


Pretest #18:

score: 0
Memory Limit Exceeded

input:

7892259 7983727

output:


result:


Pretest #19:

score: 0
Memory Limit Exceeded

input:

7937869 29796968

output:


result:


Pretest #20:

score: 0
Memory Limit Exceeded

input:

29717543 29510173

output:


result:



Final Tests

Test #1:

score: 0
Memory Limit Exceeded

input:

96 98

output:


result:


Test #2:

score: 0
Memory Limit Exceeded

input:

100 99

output:


result:


Test #3:

score: 0
Memory Limit Exceeded

input:

99 99

output:


result:


Test #4:

score: 0
Memory Limit Exceeded

input:

963 951

output:


result:


Test #5:

score: 0
Memory Limit Exceeded

input:

958 974

output:


result:


Test #6:

score: 0
Memory Limit Exceeded

input:

966 990

output:


result:


Test #7:

score: 0
Memory Limit Exceeded

input:

7958 7947

output:


result:


Test #8:

score: 0
Memory Limit Exceeded

input:

7623 7730

output:


result:


Test #9:

score: 0
Memory Limit Exceeded

input:

7845 7783

output:


result:


Test #10:

score: 0
Memory Limit Exceeded

input:

7881 7773

output:


result:


Test #11:

score: 0
Memory Limit Exceeded

input:

99414 98698

output:


result:


Test #12:

score: 0
Memory Limit Exceeded

input:

98249 96148

output:


result:


Test #13:

score: 0
Memory Limit Exceeded

input:

99003 96832

output:


result:


Test #14:

score: 0
Memory Limit Exceeded

input:

98266 96030

output:


result:


Test #15:

score: 0
Memory Limit Exceeded

input:

968207 958885

output:


result:


Test #16:

score: 0
Memory Limit Exceeded

input:

959846 998397

output:


result:


Test #17:

score: 0
Memory Limit Exceeded

input:

965821 972280

output:


result:


Test #18:

score: 0
Memory Limit Exceeded

input:

7855098 7962479

output:


result:


Test #19:

score: 0
Memory Limit Exceeded

input:

7841076 29648718

output:


result:


Test #20:

score: 0
Memory Limit Exceeded

input:

29365129 29012208

output:


result: