poj-1426 Find The Multiple

绝地灬酷狼 2022-06-01 01:17 136阅读 0赞

Find The Multiple

<table style="margin-left:0px;"> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td colspan="3"><strong>Memory Limit:</strong>&nbsp;10000K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;18390</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;7445</td> 
   <td>&nbsp;</td> 
   <td>Special Judge</td> 
  </tr> 
 </tbody> 
</table>

Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

Sample Input

[?][Link 1]

Sample Output

[?][Link 1]

题意：找一个大于等于N的数，使这个数每一位只有0和1，且能被N整除

同余模定理：找一个大于等于N的数，使这个数每一位只有0和1，且能被N整除

代码：1

#include<stdio.h>
    #define N 600000
    int mod[N];
    int ans[200];
    int main()
    {
        int i,k,n;
        while(scanf("%d",&n),n)
        {
            mod[1]=1%n; 
            for(i=2;mod[i-1]!=0;i++)
            {                    
                mod[i]=(mod[i/2]*10+i%2)%n;
            }
            i--;
            k=0;
            while(i)
            {
                ans[k++]=i%2;
                i/=2;
            }
            for(i=k-1;i>=0;i--)
                printf("%d",ans[i]);
            puts("");
        }
        return 0;
    }

代码：2

#include<stdio.h>
    #include<math.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int n,flag;
    void f( unsigned __int64 x,int n,int k )
    {
        if(flag)
            return ;
        if(x%n==0)
        {
            printf("%I64u\n",x);
            flag=1;
            return ;
        }
        if(k==19)
            return ;
        f(x*10,n,k+1);
        f(x*10+1,n,k+1);
    }
    int main()
    {
        while(scanf("%d",&n)!=EOF)
        {
            if(n==0)
                break;
            flag=0;
            f(1,n,0);
        }
    }

[Link 1]: https://www.2cto.com/kf/201410/340452.html#