UVa 10929 You can say 11

你的任務是，給你一個正整數 N，判定它是否是 11 的倍數。

Input

每列資料有一個正整數N，N 最大可能到 1000 位數。

若 N = 0 代表輸入結束。

Output

對每個輸入的數，輸出是否為 11 的倍數。輸出格式請參考 Sample Output。

 

方法1：直接从个位数开始mod 11计算。

 /*0.026s*/  
  
#include<cstdio>  
#include<cstring>  
  
char s[1005];  
  
int main(void)  
{  
    int remainder;  
    while (gets(s), strcmp(s, "0"))  
    {  
        remainder = 0;  
        for (int i = 0; s[i]; i++)  
            remainder = (remainder * 10 + (s[i] & 15)) % 11;  
        if (remainder) printf("%s is not a multiple of 11.\n", s);  
        else printf("%s is a multiple of 11.\n", s);  
    }  
    return 0;  
}

备注：&15按位与的意思 每位同时为1才为1，否则为0

 

方法2：若一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除。

证明：比如num = 10000a4+1000a3+100a2+10a1+a0=(a4+a2+a0-a3-a1)+(9999a4+99a2+1001a3+11a1)

因为11 | 99，所以11 | (9900+99)

因为11 | 1111，所以11 | (1111-110)

所以…

 /*0.025s*/  
  
#include<cstdio>  
#include<cstring>  
  
char s[1005];  
  
int main(void)  
{  
    int l, i, sum;  
    while (gets(s), strcmp(s, "0"))  
    {  
        l = strlen(s), sum = 0;  
        for (i = 0; i < l; i += 2) sum += s[i] & 15;  
        for (i = 1; i < l; i += 2) sum -= s[i] & 15;  
        if (sum % 11) printf("%s is not a multiple of 11.\n", s);  
        else printf("%s is a multiple of 11.\n", s);  
    }  
    return 0;  
}