fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4.  
  5. vector<bool> prime_bool;
  6. vector<int> prime;
  7. vector<int> spf;
  8. //seive algo for prime no.s
  9. void find_prime(int n){
  10.     int rest = n + 10;
  11.     prime_bool.assign(rest, true);
  12.     spf.assign(n+1, -1);
  13.     for(int i=2;i*i<=rest;i++){
  14.         if(prime_bool[i]==false) continue;
  15.         else{
  16.             for(int j=2*i;j<=rest;j+=i){
  17.                 prime_bool[j]=false;
  18.                 if(spf[j]==-1) spf[j] = i;
  19.             }
  20.         }
  21.     }
  22.     for(int i=2;i<=rest;i++){
  23.         if(prime_bool[i]==true){
  24.             spf[i] = i;
  25.             prime.push_back(i);
  26.         }
  27.     }
  28. }
  29.  
  30. int32_t main(){
  31.     ios_base::sync_with_stdio(false);
  32.     cin.tie(NULL);
  33.     int q;
  34.     cin>>q;
  35.     find_prime(1e6+5);
  36.     while(q--){
  37.         int a, b;
  38.         cin>>a>>b;
  39.         map<int, int> fact;
  40.         while(a>1){
  41.             fact[spf[a]]++;
  42.             a /= spf[a];
  43.         }
  44.         while(b>1){
  45.             fact[spf[b]]++;
  46.             b /= spf[b];
  47.         }
  48.         int ans = 1;
  49.         for(auto i: fact){
  50.             ans *= (2*i.second + 1);  //2 is multiplied as we have to calculte for the square
  51.         }
  52.         cout<<ans<<"\n";
  53.     }
  54. }
Success #stdin #stdout 0.03s 12204KB
comments (?)
stdin
copy 
2
2 3
4 9
stdout
copy 
9
25
https://ideone.com/9vmzGp
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!