top1编程
← 返回题目
题解

判断整除

1 条题解

  • 0
    @ 2026-7-28 22:45:08
    #include <iostream>
    #include <cstdio>
    using namespace std;
    
    /*
    状态:f(i, j) 前i个数组合 模k 可以得到余数j
    f[i][j] = 1;	前i个数组合 模k 可以得到余数j
    f[i][j] = 0;    前i个数组合 模k 不可以得到余数j
    
    if f[i - 1][j] == 1
    	f[i][(j + a[i]) % k] = 1
    */
    
    const int N = 1e4 + 10;
    
    int n, k;
    int a[N];
    int f[N][110] = {1};	// f[0][0] = 1;
    
    int main() {
      
      	cin >> n >> k;
      	for(int i = 1; i <= n; i++) {
        	cin >> a[i];
          	a[i] %= k;
        }
      
      	for(int i = 1; i <= n; i++){
        	for(int j = 0; j < k; j++)
              	if(f[i - 1][j]){
                	f[i][(j + a[i]) % k] = 1;
                  	f[i][(j - a[i] + k) % k] = 1;
                }
        }
    
    	if(f[n][0]) puts("YES");
      	else puts("NO");
      
      	/*
        k = 4
        1 2 4 = 7 => j = 3  f[3][3] = 1 
        1 2 4 5 = 12 => 0  f[4][0] = 1
        1 2 4 - 5 => f[4][2] = 1
        */
      
    	return 0;
    }
    
    • 1