2020杭電多校第三場問題解


1004 - Tokitsukaze and Multiple Problem - 6794
まず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; }