fork download
copy 
  1. //satyaki3794
  2. #include <bits/stdc++.h>
  3. #define ff first
  4. #define ss second
  5. #define pb push_back
  6. #define MOD (1000000007LL)
  7. #define LEFT(n) (2*(n))
  8. #define RIGHT(n) (2*(n)+1)
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef unsigned long long ull;
  13. typedef pair<int, int> ii;
  14. typedef pair<int, ii> iii;
  15.  
  16. ll pwr(ll base, ll p, ll mod = MOD){
  17. ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
  18. }
  19.  
  20. ll gcd(ll a, ll b){
  21.     if(b == 0)  return a;
  22.     return gcd(b, a%b);
  23. }
  24.  
  25.  
  26. int sieve[1000*1000+2], last[2][1000*1000+2];
  27. ll reduced_form[1000*1000+2], complement[1000*1000+2];
  28. ll cnt[2][1000*1000+2];
  29. set<int> distinct;
  30.  
  31.  
  32. int main(){
  33.  
  34.     ios_base::sync_with_stdio(0);
  35.  
  36.     for(int i=1;i<=1000*1000;i++)
  37.         reduced_form[i] = complement[i] = 1;
  38.  
  39.     sieve[1] = 1;
  40.     int x = 1000*1000;
  41.     for(int i=2;i<=x;i++)
  42.         if(!sieve[i]){
  43.             for(int j=i;j<=x;j+=i){
  44.                 sieve[j] = 1;
  45.                 int cnt = 0, val = j;
  46.                 while(val % i == 0){
  47.                     val /= i;
  48.                     cnt++;
  49.                 }
  50.                 cnt %= 3;
  51.         // if(j == 6)  cout<<"got "<<cnt<<" for i = "<<i<<endl;
  52.                 if(cnt != 0){
  53.                     // reduced_form[j].pb({i, cnt});
  54.                     // complement[j].pb({i, 3-cnt});
  55.                     reduced_form[j] *= pwr(i, cnt, (ll)1e15);
  56.                     complement[j] *= pwr(i, 3-cnt, (ll)1e15);
  57.                 }
  58.             }
  59.         }
  60.  
  61. // cout<<"reduced_form: ";for(int i=1;i<=20;i++)   cout<<i<<":"<<reduced_form[i]<<" ";cout<<endl;
  62. // cout<<"complement: ";for(int i=1;i<=20;i++)   cout<<i<<":"<<complement[i]<<" ";cout<<endl;
  63.  
  64.     int T;
  65.     cin>>T;
  66.     // T=1;
  67.     for(int t=1;t<=T;t++){
  68.  
  69.         distinct.clear();
  70.  
  71.         int n1, n2;
  72.         cin>>n1>>n2;
  73.  
  74.         while(n1--){
  75.             int a;
  76.             cin>>a;
  77.             int r = reduced_form[a];
  78.             if(last[0][r] != t){
  79.                 last[0][r] = t;
  80.                 cnt[0][r] = 0;
  81.             }
  82.             cnt[0][r]++;
  83.             distinct.insert(r);
  84.         }
  85.  
  86.         while(n2--){
  87.             int a;
  88.             cin>>a;
  89.             int r = reduced_form[a];
  90.             if(last[1][r] != t){
  91.                 last[1][r] = t;
  92.                 cnt[1][r] = 0;
  93.             }
  94.             cnt[1][r]++;
  95.             distinct.insert(r);
  96.         }
  97.  
  98.  
  99. // cout<<"distinct: ";for(auto it : distinct)  cout<<it<<" ";cout<<endl;
  100.  
  101.         ll ans = -1;
  102.         for(auto it : distinct){
  103.  
  104.             if(last[0][it]==t && complement[it]<=1000*1000 && last[1][complement[it]]==t)
  105.                 ans = max(ans, cnt[0][it]*cnt[0][it] + cnt[1][complement[it]]*cnt[1][complement[it]]);
  106.  
  107.             if(last[1][it]==t && complement[it]<=1000*1000 && last[0][complement[it]]==t)
  108.                 ans = max(ans, cnt[1][it]*cnt[1][it] + cnt[0][complement[it]]*cnt[0][complement[it]]);
  109.         }
  110.  
  111.         cout<<ans<<endl;
  112.     }
  113.  
  114.     return 0;
  115. }
  116.  
  117.  
  118.  
  119.  
  120.  
Runtime error #stdin #stdout 0.18s 46440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xAwZhK
language:
C++14 (gcc 8.3)
created:
8 years 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!