2020杭電多校第三場問題解
1004 - Tokitsukaze and Multiple Problem - 6794
まずn、pをあげて、それからnの数字、2つの数字は合并することができて、最后に最大でどれだけの数字がpの倍数になることができますかを闻きます.
考え方:接頭辞と時間を節約して、前に同じモジュールが現れたかどうかを探して、この2つの間に1つの除去ができることを証明します.
まずn、pをあげて、それからnの数字、2つの数字は合并することができて、最后に最大でどれだけの数字がpの倍数になることができますかを闻きます.
考え方:接頭辞と時間を節約して、前に同じモジュールが現れたかどうかを探して、この2つの間に1つの除去ができることを証明します.
#include
using namespace std;
const int MAXX = 1e5+10;
int a[MAXX];
map<int,int> m;
int main() {
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int o;
cin>>o;
while(o--){
m.clear();
int n,p;
cin>>n>>p;
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]=(a[i]+a[i-1])%p;
}
int ans = 0;
m[0]++;
for(int i=1; i<=n; i++){
map<int,int> :: iterator it;
it = m.find(a[i]);
if(it!=m.end()){
ans++;
m.clear();
}
m[a[i]]++;
}
cout<<ans<<"
";
}
return 0;
}