[C/C++] 백준 3673번 - 나눌 수 있는 부분 수열

 

 

 

<코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<memory.h>
using namespace std;

int c,d,n;
long long sum, x, ans;
long long arr[1000001];

int main() 
{
	ios::sync_with_stdio(0); 
	cin.tie(0); 

	cin >> c;
	

	while (c--)
	{
		cin >> d >> n;
		sum = 0;

		for (int i = 0; i < n; i++)
		{
			cin >> x;
			sum += x;
			arr[sum % d]++;
		}

		ans = arr[0];

		for (int i = 0; i < d; i++)
		{
			ans += arr[i] * (arr[i] - 1) / 2;
		}
		cout << ans << '\n';
		memset(arr, 0, sizeof(arr));
	}

}

 

풀이 방법

비슷한 문제 풀이법

cocoon1787.tistory.com/396

[C/C++] 백준 10986번 - 나머지 합

 

 

 

 

www.acmicpc.net/problem/3673

3673번: 나눌 수 있는 부분 수열