?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
126669391 |
Practice: SkyWalkerPS |
1535B - 23 | C++17 (GCC 7-32) | Time limit exceeded on test 2 | 2000 ms | 3784 KB | 2021-08-22 09:39:55 | 2021-08-22 09:39:55 |
////SkyWalker/// #include<bits/stdc++.h> #define ll long long #define ld long double #define fir(i, a, b) for(int i=a;i<b;i++) #define rfir(i, a, b) for(int i=a;i>=b;i--) #define lb lower_bound #define ub upper_bound #define bs binary_search #define mod 1000000007 #define fast \ ios_base::sync_with_stdio(0); \ cin.tie(0); \ cout.tie(0); #define tests \ int tt; \ cin>>tt; while(tt--) using namespace std; /****************************/ /* const int N = 1e6+1; bool arr[N]; void process(){ fir(i, 0, N)arr[i]=true; for(int i=2; i*i<=N; i++){ if(arr[i]==true){ for(int j=i*i; j<N; j+=i){ arr[j]=false; } } } } */ int main() { fast; tests{ int n; cin>>n; int arr[n]; vector<int>odd; int even=0; fir(i, 0, n){ cin>>arr[i]; if(arr[i]%2==0){ even++; } else{ odd.push_back(arr[i]); } } int ans = even*odd.size() + even*(even-1)/2; fir(i, 0, odd.size()-1){ fir(j, i+1, odd.size()){ if(__gcd(odd[i], odd[j])!=1){ ans++; } } } cout<<ans<<endl; } return 0; }
?
?
?
?