結果
問題 | No.2260 Adic Sum |
ユーザー |
|
提出日時 | 2023-04-07 21:30:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 116 ms / 2,000 ms |
コード長 | 619 bytes |
コンパイル時間 | 785 ms |
コンパイル使用メモリ | 82,228 KB |
実行使用メモリ | 14,208 KB |
最終ジャッジ日時 | 2024-10-06 07:01:30 |
合計ジャッジ時間 | 3,784 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include<iostream> #include<vector> #include<map> using namespace std; int P; long ans; void solve(const vector<int>&A) { if(A.size()<=1)return; if(A.size()<=30) { for(int i=0;i<A.size();i++)for(int j=i+1;j<A.size();j++) { int d=abs(A[i]-A[j]); while(d%P==0)d/=P,ans++; } return; } map<int,vector<int> >mp; for(int i=0;i<A.size();i++)mp[A[i]%P].push_back(A[i]/P); for(auto it=mp.begin();it!=mp.end();it++) { int n=it->second.size(); ans+=(long)n*(n-1)/2; solve(it->second); } } int main() { int N;cin>>N>>P; vector<int>A(N); for(int i=0;i<N;i++)cin>>A[i]; solve(A); cout<<ans<<endl; }