Submission #7747566


Source Code Expand

Copy
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define mp make_pair
#define ins insert
#define sb substr
#define con continue
#define ub upper_bound
#define lb lower_bound
#define sp fixed<<setprecision
#define bp __builtin_popcountll
#define pll pair<ll,ll>
#define pld pair<ld,ld>
using namespace std;

ll power(ll x, ll y);
ll mpower(ll x, ll y, ll p);
ll modInv(ll a, ll m);
ll gcdExtended(ll a, ll b, ll *x, ll *y);
bool isPrime(ll n);

ll A[1000001];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll t,i,j,k,l,h,p,q,r,x,y,z,a,b,c,d,f,n,m,M=1000000007;
    char ch,ch2,ch3;
    string s,s1,s2,s3;
    vector<ll> v,w;
    unordered_map<ll,ll> N;
    set<ll> S;
    set<ll> :: iterator itr;
    cin>>x>>y;
    p=__gcd(x,y);
    for(i=2;i<1000001;i++){
        if(!A[i]){
            for(j=i+i;j<1000001;j+=i){
                A[j]=1;
            }
        }
    }
    c=1;
    for(i=2;i<1000001;i++){
        if(A[i]){
            con;
        }
        if(p%i==0){
            c++;
            while(p%i==0){
                p/=i;
            }
        }
    }
    if(p>1){
        c++;
    }
    cout<<c;
    return 0;
}

ll modInv(ll a, ll m){
    ll x, y;
    ll g = gcdExtended(a, m, &x, &y);
    ll res = (x%m + m) % m;
    return res;
}

ll gcdExtended(ll a, ll b, ll *x, ll *y){
    if (a == 0){
        *x = 0, *y = 1;
        return b;
    }
    ll x1, y1;
    ll gcd = gcdExtended(b%a, a, &x1, &y1);
    *x = y1 - (b/a) * x1;
    *y = x1;
    return gcd;
}

ll mpower(ll x, ll y, ll p){
    ll res = 1;
    x = x % p;
    while(y > 0){
        if(y & 1) res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}

ll power(ll x, ll y){
    ll res = 1;
    while (y > 0){
        if (y & 1) res = res*x;
        y = y>>1;
        x = x*x;
    }
    return res;
}

bool isPrime(ll n){
    if (n <= 1)  return false;
    if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    ll p=sqrt(n);
    for(int i=5;i<=p;i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
            return false;
    return true;
}

Submission Info

Submission Time
Task D - Disjoint Set of Common Divisors
User sardhara_preet
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2277 Byte
Status AC
Exec Time 15 ms
Memory 8064 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 15 ms 8064 KB
sample_02 AC 15 ms 8064 KB
sample_03 AC 15 ms 8064 KB
testcase_01 AC 15 ms 8064 KB
testcase_02 AC 15 ms 8064 KB
testcase_03 AC 15 ms 8064 KB
testcase_04 AC 15 ms 8064 KB
testcase_05 AC 15 ms 8064 KB
testcase_06 AC 15 ms 8064 KB
testcase_07 AC 15 ms 8064 KB
testcase_08 AC 15 ms 8064 KB
testcase_09 AC 15 ms 8064 KB
testcase_10 AC 15 ms 8064 KB
testcase_11 AC 15 ms 8064 KB
testcase_12 AC 15 ms 8064 KB
testcase_13 AC 15 ms 8064 KB
testcase_14 AC 15 ms 8064 KB
testcase_15 AC 15 ms 8064 KB
testcase_16 AC 15 ms 8064 KB
testcase_17 AC 15 ms 8064 KB
testcase_18 AC 15 ms 8064 KB
testcase_19 AC 15 ms 8064 KB
testcase_20 AC 15 ms 8064 KB
testcase_21 AC 15 ms 8064 KB
testcase_22 AC 15 ms 8064 KB
testcase_23 AC 14 ms 8064 KB