Submission #7747509


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

set<long long> prime_factor(long long n) {
	set<long long> res;
	res.insert(1);
	for (long long i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			res.insert(i);
			n /= i;
			// cout << i << " " << n << endl;
		}
	}
	if (n != 1) res.insert(n);
	return res;
}

long long extgcd(long long a, long long b, long long& x, long long& y) {
	long long d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	} else {
		x = 1; y = 0;
	}
	return d;
}

void solve(long long A, long long B){
	ll x, y, g;
	g = extgcd(A, B, x, y);
	cout << prime_factor(g).size() << endl;
}

int main(){	
	long long B;
	long long A;
	scanf("%lld",&A);
	scanf("%lld",&B);
	solve(A, B);
	return 0;
}

Submission Info

Submission Time
Task D - Disjoint Set of Common Divisors
User dn154
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1439 Byte
Status AC
Exec Time 11 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:58:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&A);
                  ^
./Main.cpp:59:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&B);
                  ^

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 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 1 ms 256 KB
testcase_01 AC 1 ms 256 KB
testcase_02 AC 1 ms 256 KB
testcase_03 AC 4 ms 256 KB
testcase_04 AC 1 ms 256 KB
testcase_05 AC 1 ms 256 KB
testcase_06 AC 1 ms 256 KB
testcase_07 AC 1 ms 256 KB
testcase_08 AC 1 ms 256 KB
testcase_09 AC 1 ms 256 KB
testcase_10 AC 1 ms 256 KB
testcase_11 AC 1 ms 256 KB
testcase_12 AC 1 ms 256 KB
testcase_13 AC 1 ms 256 KB
testcase_14 AC 1 ms 256 KB
testcase_15 AC 1 ms 256 KB
testcase_16 AC 1 ms 256 KB
testcase_17 AC 1 ms 256 KB
testcase_18 AC 1 ms 256 KB
testcase_19 AC 1 ms 256 KB
testcase_20 AC 2 ms 256 KB
testcase_21 AC 2 ms 256 KB
testcase_22 AC 2 ms 256 KB
testcase_23 AC 11 ms 256 KB