Submission #7750878


Source Code Expand

Copy
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <complex>

using namespace std;
using pii = pair<int, int>;
using ll = long long;

ll gcd(ll a, ll b)
{
	return (b == 0) ? a : gcd(b, a % b);
}

bool isp(ll n)
{
	if (n % 2 == 0) return false;
	ll sqn = sqrt(n);
	for (ll i = 3; i <= sqn; i += 2) if (n % i == 0) return false;
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	vector<int> era(1000001);
	era[1] = era[2] = 1;
	for (int i = 3; i <= 1000000; i += 2) {
		if (era[i] == 0) {
			era[i] = 1;
			for (int j = i + i; j <= 1000000; j += i) era[j] = -1;
		}
	}

	ll a, b;
	cin >> a >> b;
	ll g = gcd(a, b);

	ll sqg = sqrt(g);
	int answer = 0;
	for (ll i = 1; i <= sqg; i++) {
		if (g % i == 0) {
			if (era[i] == 1) answer += 1;
			if (i != g / i && isp(g / i)) answer += 1;
		}
	}
	cout << answer;
	
	return 0;
}

Submission Info

Submission Time
Task D - Disjoint Set of Common Divisors
User ParkJH
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1100 Byte
Status AC
Exec Time 26 ms
Memory 4224 KB

Judge Result

Set Name All Sample
Score / Max Score 400 / 400 0 / 0
Status
AC × 26
AC × 3
Set Name Test Cases
All sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18, testcase_19, testcase_20, testcase_21, testcase_22, testcase_23
Sample sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 AC 9 ms 4224 KB
sample_02 AC 9 ms 4224 KB
sample_03 AC 9 ms 4224 KB
testcase_01 AC 9 ms 4224 KB
testcase_02 AC 9 ms 4224 KB
testcase_03 AC 20 ms 4224 KB
testcase_04 AC 10 ms 4224 KB
testcase_05 AC 13 ms 4224 KB
testcase_06 AC 12 ms 4224 KB
testcase_07 AC 9 ms 4224 KB
testcase_08 AC 9 ms 4224 KB
testcase_09 AC 9 ms 4224 KB
testcase_10 AC 10 ms 4224 KB
testcase_11 AC 17 ms 4224 KB
testcase_12 AC 19 ms 4224 KB
testcase_13 AC 9 ms 4224 KB
testcase_14 AC 19 ms 4224 KB
testcase_15 AC 14 ms 4096 KB
testcase_16 AC 17 ms 4224 KB
testcase_17 AC 18 ms 4224 KB
testcase_18 AC 19 ms 4224 KB
testcase_19 AC 11 ms 4224 KB
testcase_20 AC 11 ms 4224 KB
testcase_21 AC 10 ms 4224 KB
testcase_22 AC 11 ms 4224 KB
testcase_23 AC 26 ms 4224 KB