2010-1132

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题目大意：为对一个整数N，求N的倍数中能用最少数字表示的数，有小于等于8位时输出最小的这种倍数，否则随意输入一个这种倍数。

可以证明，N的倍数中总有只含有0和1的数。[[BR]]
如下表1[[BR]]
11[[BR]]
111[[BR]]
1111[[BR]]
11111[[BR]]
……

列出N+1行后，总有两行的余数相等，这两行的差就是一个只用0和1表示的N的倍数。这样就可以直接构造一个这种数[[BR]]
对于小于等于8位的情况，因为这类数只有512个，所以可以直接枚举。

代码如下:

{{{
#!cpp
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int base[10]={1,10,100,1000,10000,100000,1000000,10000000};
int turn(int t)
{
    int ret=0,k=0;
    while (t>0)
    {
        if (t%2)
        {
            ret+=base[k];
        }
        k++;
        t/=2;
    }
    return ret;
}
int mod[100000];
void invalid_output(int n)
{
    int k=1,d=1,i;
    while (k!=0 && mod[k]==0)
    {
        mod[k]=d;
        k*=10;
        k+=1;
        k%=n;
        d++;
    }
//  printf("%d %d\n",d,mod[k]);
    cout<<"Invalid ";
    for (i=d;i>mod[k];i--) printf("1");
    for (i=mod[k];i>0;i--) printf("0");
    cout<<" (Base 2)"<<endl;
}
int main()
{
    int n,t,x,i;
    bool finish;
    while (cin>>n)
    {
        memset(mod,0,sizeof(mod));
        finish=false;
        for (t=1;t<256;t++)
        {
            x=turn(t);
            if (x%n==0) 
            {
                finish=true;
                break;
            }
        }
        if (finish)
            cout<<"Valid "<<x<<" (Base 2)"<<endl;
        else
            invalid_output(n);
    }
    return 0;
}
}}}
by pxhdg

题目大意：为对一个整数N，求N的倍数中能用最少数字表示的数，有小于等于8位时输出最小的这种倍数，否则随意输入一个这种倍数。

可以证明，N的倍数中总有只含有0和1的数。

如下表1

11

111

1111

11111

……

列出N+1行后，总有两行的余数相等，这两行的差就是一个只用0和1表示的N的倍数。这样就可以直接构造一个这种数

对于小于等于8位的情况，因为这类数只有512个，所以可以直接枚举。

代码如下:

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int base[10]={1,10,100,1000,10000,100000,1000000,10000000};
int turn(int t)
{
    int ret=0,k=0;
    while (t>0)
    {
        if (t%2)
        {
            ret+=base[k];
        }
        k++;
        t/=2;
    }
    return ret;
}
int mod[100000];
void invalid_output(int n)
{
    int k=1,d=1,i;
    while (k!=0 && mod[k]==0)
    {
        mod[k]=d;
        k*=10;
        k+=1;
        k%=n;
        d++;
    }
//  printf("%d %d\n",d,mod[k]);
    cout<<"Invalid ";
    for (i=d;i>mod[k];i--) printf("1");
    for (i=mod[k];i>0;i--) printf("0");
    cout<<" (Base 2)"<<endl;
}
int main()
{
    int n,t,x,i;
    bool finish;
    while (cin>>n)
    {
        memset(mod,0,sizeof(mod));
        finish=false;
        for (t=1;t<256;t++)
        {
            x=turn(t);
            if (x%n==0) 
            {
                finish=true;
                break;
            }
        }
        if (finish)
            cout<<"Valid "<<x<<" (Base 2)"<<endl;
        else
            invalid_output(n);
    }
    return 0;
}

by pxhdg