1195：判斷整除

時間限制: 1000 ms ??? ??? 內存限制: 65536 KB
提交數: 9531 ??? 通過數: 3952

【題目描述】

一個給定的正整數序列，在每個數之前都插入+號或?號后計算它們的和。比如序列：1、2、4共有8種可能的序列：

(+1) + (+2) + (+4) = 7 (+1) + (+2) + (-4) = -1 (+1) + (-2) + (+4) = 3 (+1) + (-2) + (-4) = -5 (-1) + (+2) + (+4) = 5 (-1) + (+2) + (-4) = -3 (-1) + (-2) + (+4) = 1 (-1) + (-2) + (-4) = -7

所有結果中至少有一個可被整數k整除，我們則稱此正整數序列可被k整除。例如上述序列可以被3、5、7整除，而不能被2、4、6、8……整除。注意：0、?3、?6、?9……0、?3、?6、?9……都可以認為是3的倍數。

【輸入】

輸入的第一行包含兩個數：N(2<N<10000)和k(2<k<100)，其中N代表一共有N個數，k代表被除數。第二行給出序列中的N個整數，這些整數的取值范圍都0到10000之間（可能重復）。

【輸出】

如果此正整數序列可被k整除，則輸出YES，否則輸出NO。（注意：都是大寫字母）

【輸入樣例】

3 2 1 2 4

【輸出樣例】

NO

【分析】

? ? ? ? 設變量fi,j表示前 i 個數的和是否可以被 j（0不可以，1可以），如果要轉移到fi,j的狀態，那么就要在前i-1個數已經入列的基礎上再加第 i 個數，而第 i 個數又只有正和負兩種情況，所以只考慮是由加第 i 個數 和 減第 i 個數就好了。

? ? ? ? 要想加ai得到余數為 j 的情況，那么前 i-1個數必須滿足余數可以為 j-ai。反之，若減ai得到余數可以為 j，那么前 i-1個數必須滿足余數可以為j+ai。所以，要想ai入列后，余數為j，那么上述兩個條件滿足一個就好。

? ? ? ? 列方程：fi,j = fi-1,j-ai? ||? fi-1,j+ai? ? ? ?

? ? ? ? 邊界條件：f0,0=1(0個元素，結果為零，所以不管k為多少，余數都為零)

感謝題解：https://www.cnblogs.com/Wild-Donkey/p/12219856.html

【參考代碼】

#include <stdio.h> #define N 10010 #define M 110 int a[N]; int f[N][M]; int main() {int i,j,k,n,tmp;scanf("%d%d",&n,&k);for(i=1;i<=n;i++){scanf("%d",&tmp);tmp%=k;a[i]=tmp;}f[0][0]=1; //遞推邊界for(i=1;i<=n;i++)for(j=0;j<k;j++)f[i][j]=(f[i-1][(j-a[i]+k)%k]||f[i-1][(j+a[i]+k)%k]); //遞推公式 if(f[n][0])printf("YES\n");elseprintf("NO\n");return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1195

?

?

總結

以上是生活随笔為你收集整理的信息学奥赛一本通（1195：判断整除）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。