nyoj1086是否被整除（數學小技巧）

nyoj1086是否被整除（數學小技巧）

是否被整除

描述

一個位數不大於100萬位的正整數，如果它既能被11整除又能被2的n次方整除就輸出YES否則輸出NO

輸入

輸入有多組數據每組數據有兩行
第一行一個n代表2的n次方（0 第二行一個整數

輸出

輸出只有一行每行一個YES或NO

樣例輸入

1
110
2
1100
3
110

樣例輸出

YES
YES
NO

來源

原創

上傳者

TC_蔣鑫博

思路：能被2的N次方的數整除的數的特征
如果一個數末N位能被2的N次方的數整除，那麼這個數就能被2的N次方的這個數整除。
如能被8（2的3次方）整除的數的特征：這個數字的末三位能被8整除。
能被11整除的數的特征
把一個數由右邊向左邊數,將奇位上的數字與偶位上的數字分別加起來,再求它們的差,如果這個差是11的倍數(包括0),那麼,原來這個數就一定能被11除.
例如:判斷491678能不能被11整除. —→奇位數字的和9+6+8=23
—→偶位數位的和4+1+7=12
23-12=11 因此,491678能被11整除. 這種方法叫"奇偶位差法".

#include
#include
#include
#include
using namespace std;
int a[22]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576};
int main()
{
    int n;
    char s[1000005];
    char ss[1000005];
    while(cin>>n>>s)
    {
        int l=strlen(s);
        int k=0;
        for(int i=l-n;i