結果
問題 |
No.1746 Sqrt Integer Segments
|
ユーザー |
![]() |
提出日時 | 2021-11-19 07:58:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,265 bytes |
コンパイル時間 | 2,400 ms |
コンパイル使用メモリ | 206,888 KB |
最終ジャッジ日時 | 2025-01-25 19:31:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 3 TLE * 9 MLE * 16 |
ソースコード
#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; #include <bits/stdc++.h> using namespace std; template<typename T> vector<T> smallest_prime_factors(T n){ vector<T> spf(n+1); for(int i=0;i<=n;i++) spf[i]=i; for(T i=2;i*i<=n;i++){ if(spf[i]==i){ for(T j=i*i;j<=n;j+=i){ if(spf[j]==j) spf[j]=i; } } } return spf; } template<typename T> vector<T> factolization(T x,vector<T> &spf){ vector<T> ret; while(x!=1) { ret.push_back(spf[x]); x/=spf[x]; } sort(ALL(ret)); return ret; } bitset<80000> B[200200]; int C[1000100]; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); constexpr int MAX=1000100; auto spf=smallest_prime_factors(MAX); int n; cin>>n; vector<int> A(n); rep(i,n) cin>>A[i]; int cnt=0; for(int i=2;i<=1000000;i++){ if(spf[i]==i){ C[i]=cnt; cnt++; } } ll ans=0; string a; rep(i,80000) a+='0'; string now=a; map<string,ll> M; rep(i,n){ auto result=factolization(A[i],spf); for(auto t:result){ if(now[C[t]]=='0') now[C[t]]='1'; else now[C[t]]='0'; } ans+=M[now]; if(now==a) ans++; M[now]++; } cout<<ans<<endl; return 0; }