摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

在此感謝:B88000005 提供想法

作法:數學

證明:

2^0%3=1
2^1%3=2
2^2%3=1
2^3%3=2
.
.
.
以此類推
為什麼這樣子呢?
2^0%3=商*3+1
2^1%3=商*3+2   <<<把這些想成 3*n+m
2^2%3=商*3+1   <<<每次乘2變成 3*2n+2m
2^3%3=商*3+2   <<<2m又再次%3 所以才會造成 1 2 1 2 1 2的循環
.
.
.
以此類推
隨機抽出來幾個來的話
便是二進位,變成(商的加總)*3+(所有餘數的合)<<<只要這裡為3個倍數 答案就是YES
之後這個二進位,就是3*(某數) <<<提出公因數

想法:

先把二進位顛倒,再來是奇數若為1則+2,偶數若為1則+1

若總和%3==0 就是3的倍數

EX : 輸入1101→倒過來1011

現在分析1011

讀到第1個數字 因為它為1且為奇數 sum=sum+2;
讀到第2個數字 為0不做
讀到第3個數字 因為它為1且為奇數 sum=sum+2;
讀到第4個數字 因為它為1且為偶數 sum=sum+1;

sum=2+2+1=5 %3!=0 所以不是!!

1101=1+2^2+2^3=1+4+8=13

在此提供3種版本
由於輸入很大筆 造成一點點的 if 速度也會差很多
所以版本1較慢 版本2較快 版本3更快

 ※　用GETS讀取超快<- 2009/11/6 新增版本4

/**********************************************************/

#include<stdio.h>  
#include<stdlib.h>
#include<string.h>
main()
{
  int t;
  while(scanf("%d",&t)==1)
      while(t--)
        {
           char x[9999]={0};
           scanf("%s",x);
           int m=strlen(x),a,b,sum=0;
           for(a=0,b=m-1;b>=0;a++,b--)
            {
             if(a%2==0&&x[b]=='1') {sum=sum+2;}
             else if(a%2==1&&x[b]=='1') {sum=sum+1;}
            }
           if(sum%3==0) printf("Yes\n");
           else printf("No\n");
        }
 return 0;    
}

/*******************************************************/

#include<stdio.h>  
#include<stdlib.h>
#include<string.h>
main()
{
  int t;
  while(scanf("%d",&t)==1)
      while(t--)
        {
           char x[9001]={0};
           scanf("%s",x);
           int m=strlen(x),a,b,sum=0;
           for(a=0,b=m-1;b>=0;a=a+2,b=b-2)
             sum=sum+(x[b]-48)*2;
           for(a=1,b=m-2;b>=0;a=a+2,b=b-2)
             sum=sum+(x[b]-48)*1;
           if(sum%3==0) printf("Yes\n");
           else printf("No\n");
        }
 return 0;    
}
/***********************************************************/

#include<stdio.h>     
#include<stdlib.h>  
#include<string.h>  
main()  
{  
  int t;  
  char x[9001]={0};  
  while(scanf("%d",&t)==1)  
      while(t--)  
        {   
           scanf("%s",x);  
           int m=strlen(x),a,b,sum=0;  
           for(a=m-2,b=m-1;b>=0;b=b-2,a=a-2)  
            {
             sum=sum+(x[b]-48)*2;  
             sum=sum+(x[a]-48);  
            }
           if(a>=0) sum=sum+(x[0]-48);
           if(sum%3==0) printf("Yes\n");  
           else printf("No\n");  
        }  
 return 0;       
}

/*******************************************/

#include<stdio.h>     
#include<stdlib.h>  
#include<string.h>  
main()  
{  
  int t;  
  char x[9001]={0};  
  while(scanf("%d ",&t)==1)  
      while(t--)  
        {   
           gets(x);  
           int m=strlen(x),a,b,sum=0;  
           for(a=m-2,b=m-1;b>=0;b=b-2,a=a-2)  
            {
             sum=sum+(x[b]-48)*2;  
             sum=sum+(x[a]-48)*1;  
            }
            if(a>=0) sum=sum+(x[0]-48)*1;
           if(sum%3==0) printf("Yes\n");  
           else printf("No\n");  
        }  
 return 0;       
}