fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
  4. #define ll long long
  5. #define vll vector<ll>
  6. #define vvll vector<vll>
  7. #define FOR(i,a,b) for(ll i = a;i<b;i++)
  8. #define pll pair<ll,ll>
  9. #define pii pair<int,int>
  10. #define pb push_back
  11. #define Ye cout<<"YES\n"
  12. #define No cout<<"NO\n";
  13. void in(int n, int a[]){
  14.     for(int i = 0;i<n;i++){
  15.         cin >> a[i];
  16.     }
  17. }
  18. void out(int n, int a[]){
  19.     for(int i = 0;i<n;i++){
  20.         cout << a[i] << " ";
  21.     }
  22. }
  23. const int maxn = 2e5+5;
  24. const int maxp = 1e7+5;
  25. int spf[maxp];
  26. void sieve(){
  27.     for(int i = 0;i<maxp;i++){
  28.         spf[i] = i;
  29.     }
  30.     for(int i = 2;i*i<maxp;i++){
  31.         if(spf[i] == i){
  32.             for(int j = i*i;j<maxp;j+=i){
  33.                 if(spf[j] == j){
  34.                     spf[j] = i;
  35.                 }
  36.             }
  37.         }
  38.     }
  39. }
  40. namespace u{
  41.     int n,k;
  42.     int a[maxn];
  43.     int mask[maxn];
  44.     void solve(){
  45.         cin >> n >> k;
  46.         in(n,a);
  47.         for(int i = 0;i<n;i++){
  48.             mask[i] = 0;
  49.         }
  50.         vector<vector<pair<int,int>>> f(n+5,vector<pair<int,int>>());
  51.         //phan tich thua so nguyen to
  52.         for(int i = 0;i<n;i++){
  53.             int x = a[i];
  54.             if(x<2){
  55.                 f[i].push_back({1,1});
  56.             }
  57.             while(x>1){
  58.                 int p = spf[x];
  59.                 int cnt = 0;
  60.                 while(x%p==0){
  61.                     cnt++;
  62.                     x/=p;
  63.                 }
  64.                 f[i].push_back({p,cnt});
  65.             }
  66.         }
  67.         //tinh mask
  68.         for(int i = 0;i<n;i++){
  69.             int h = 1;
  70.             for(int j = 0;j<(int)f[i].size();j++){
  71.                 int p = f[i][j].first;
  72.                 int q = f[i][j].second%2;
  73.                 if(q == 1){
  74.                     h*=p;
  75.                 }
  76.             }
  77.             mask[i] = h;
  78.         }
  79.         int l = 0; int r = 0;
  80.         int ans = 0;
  81.         while(l<=r && r < n){
  82.             map<int,int> cnt;
  83.             while(cnt.find(mask[r]) == cnt.end() && r < n){
  84.                 cnt[mask[r]]++;
  85.                 r++;
  86.             }
  87.             l = r;
  88.             ans++;
  89.         }
  90.         cout << ans << "\n";
  91.     }
  92. }
  93. signed main(){
  94.     fast;
  95.     sieve();
  96.     int t = 1; cin >> t;
  97.     while(t--) u::solve();
  98. }
Success #stdin #stdout 0.12s 44144KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/SWkKh0
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

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!