题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=4662

题目是问目标串能否由MI得到，我们可以逆向思维，目标串能否反过来处理得到MI，所以，首先排除M没有出现或者出现超过一次，或者只出现了一次但没有出现在第一个位置的情形····也就是说只剩下第一个位置是M，然后不再出现M的情形····

接下来思考如何得到I，既然要得到I，U必然要化成I，一个U相当于3个I，接下来还可以每次添加UU，相当于添加了6个I,这样当I的个数能凑成2^k,k>=0时，就是解

问题转化为如下：

关于x + 6*y = 2^k中x的整数解

问题描述：

当x取何值时，一定能找到一对y,k,其中y>=0,k>=0,y,k都是整数，来满足 x + 6*y = 2^k。

答案：

x= 1,或者x%6 =2 或者x%6 =4.

证明：

显然当x = 1时，y=0,z=0时满足条件，x=1是解。

现在只考虑x>1的情形。

当x>1时，如果x为解。

那么x = 2^k-6*y。k>0····

注意到8%6 = 2

那么k个2(k>0)相乘后的积%6 一定为2或4。

那么x%6 = (2^k-6*y)%6 = 2^k %6 = 2或4。

这就证明了如果x是解，要么x =1,否则x%6=2或4.

那么是不是凡是%6=2或4的就一定是解呢···答案是肯定的。

先考虑2+6*q的情形

2+6*q+6*y = 2^k

3(q+y)+1 = 2^p , p =k-1

注意要4%3=1，由此得到2^(2t)%3 = 1,2^(2t+1)%3 = 2.

上面的式子必然成立。

4+6*q的情形同样可以证明。

事实上，可以从另外一个角度思考，1必然是解,当x>=1时，如果(2^k-x)%6=2^k%6 - x%6 = 0,，注意到2^k%6=2或4，所以除非x%6=2或者4，否则等式不会成立

贴代码：

 #include <cstdio>

 #include <cstring>

 #define N 1000007

 char a[N];

 int main()

 {

 //    freopen("in.c","r",stdin);

     int n;

     scanf("%d",&n);

     for(int i=; i<n; ++i)

     {

         scanf("%s",a);

 //        printf("%s\n",a);

         int len=strlen(a);

         int cnt =;

         if(a[] !='M')

         {

             printf("No\n");

             continue;

         }

         bool flag = true;

         for(int j=; j<len; ++j)

         {

             if(a[j] == 'M')

             {

                 flag = false;

                 break;

             }

             if(a[j] == 'U')

                 cnt += ;

             else

                 ++cnt;

         }

         if(!flag)

         {

             printf("No\n");

             continue;

         }

         if(cnt == )

         {

             printf("Yes\n");

             continue;

         }

 //        printf("cnt=%d\n",cnt);

         if(cnt% ==  || cnt% == )

             flag =true;

         else flag =false;

         if(flag)

             printf("Yes\n");

         else

             printf("No\n");

     }

     return ;

 }

巴特西

HDU 4662 MU Puzzle 数论或者水题

题目链接：

问题描述：

答案：

证明：

最新文章

热门文章