LightOJ – Mysterious Bacteria

L
Problem NameMysterious Bacteria
JudgeLightOJ
Problem Linkhttps://lightoj.com/problem/mysterious-bacteria
Algorithms & DSPrime Factorization, GCD
#include<bits/stdc++.h> using namespace std; typedef long long ll; constexpr ll MX = 1e6; bitset<1000010>bs; vector<ll>primes; void sieve() { bs.set(); bs[0]=bs[1]=0; primes.push_back(2); for(ll i=4;i<=MX;i+=2)bs[i]=0; for(ll i=3;i<=MX;i+=2){ if(bs[i]){ primes.push_back(i); for(ll j=i*i;j<=MX;j+=i)bs[j]=0; } } } int main() { sieve(); ll t; cin>>t; ll x; for(ll T=1;T<=t;T++){ cin>>x; bool pos=true; if(x<0)pos=false; x=abs(x); cout<<"Case "<<T<<": "; vector<ll>pf; ll num=x; for(ll i=0;primes[i]*primes[i]<=num;i++){ if(num%primes[i]==0){ pf.push_back(primes[i]); while(num%primes[i]==0){ num/=primes[i]; } } } if(num>1)pf.push_back(num); ll ct=0; ll len=pf.size(); ll arr[len+5]; for(ll i=0;i<len;i++){ arr[i]=0; while(x%pf[i]==0){ x/=pf[i]; arr[i]++; } } ll g=arr[0]; for(ll i=1;i<len;i++){ g=__gcd(g,arr[i]); } if(!pos){ while(g%2==0)g/=2; } cout<<g<<"\n"; } return 0; }
Code language: PHP (php)

About the author

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!