Toph Number theory Problem Fast Co-Prime Solution
Solve in C++:
///**********ALLAH IS ALMIGHTY************/// ///AH Tonmoy ///Department of CSE ///Islamic University,Bangladesh #include<iostream> #include<vector> using namespace std; #define M 10001000 #define ll long long bool marked[M]; vector<ll>vec; void sieve() { for(ll i=3; i*i<=10000000; i+=2) { if(marked[i]==false) { for(ll j=i*i; j<=10000000; j+=2*i) { marked[j]=true; } } } vec.push_back(2); for(ll i=3; i<=10000000; i=i+2) { if(marked[i]==false) { vec.push_back(i); } } } void result(ll n,ll k) { ll s=n; ll i=0; ll sz=vec.size(); ll v=n; while(i<sz&&vec[i]*vec[i]<=v) { if((v%vec[i])==0) { s=s-(s/vec[i]); while((v%vec[i])==0) { v=(v/vec[i]); } } i++; } if(v>1) { s=s-(s/v); } s=s*(k-1); cout<<s<<endl; } main() { ll m,k,t; sieve(); cin>>t; while(t--) { scanf("%lld %lld",&m,&k); result(m,k); } }
///**********ALLAH IS ALMIGHTY************/// ///AH Tonmoy ///Department of CSE ///Islamic University,Bangladesh #include<iostream> #include<vector> using namespace std; #define M 10001000 #define ll long long bool marked[M]; vector<ll>vec; void sieve() { for(ll i=3; i*i<=10000000; i+=2) { if(marked[i]==false) { for(ll j=i*i; j<=10000000; j+=2*i) { marked[j]=true; } } } vec.push_back(2); for(ll i=3; i<=10000000; i=i+2) { if(marked[i]==false) { vec.push_back(i); } } } void result(ll n,ll k) { ll s=n; ll i=0; ll sz=vec.size(); ll v=n; while(i<sz&&vec[i]*vec[i]<=v) { if((v%vec[i])==0) { s=s-(s/vec[i]); while((v%vec[i])==0) { v=(v/vec[i]); } } i++; } if(v>1) { s=s-(s/v); } s=s*(k-1); cout<<s<<endl; } main() { ll m,k,t; sieve(); cin>>t; while(t--) { scanf("%lld %lld",&m,&k); result(m,k); } }
No comments