Find The Multiple 二叉树哈夫曼编码经典，，，同余方程（(ab)%n=(a%nb%n)%n (a+b)%n=(a%n+b%n)%n）...

谁践踏了优雅 2022-01-05 15:29 209阅读 0赞

Problem 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

Sample Output

100100100100100100

111111111111111111

\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*

![AJVnEj.png][]大神图片经典 领教啦！！

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<string>
     3 #include<cstring>
     4 #include<cmath>
     5 #include<cstdio>
     6 #include<queue>
     7 using namespace std;
     8 int mod[600001],res[600001];
     9 int n,i,j,k;
    10 int cnt;
    11 int main()
    12 {
    13    while(scanf("%d",&n)&&n)
    14    {
    15       mod[1]=1%n;
    16       for(i=2;mod[i-1];i++)
    17       {
    18           mod[i]=(mod[i/2]*10+i%2)%n;//哈夫曼树，模仿双向bfs();
    19       }
    20       i--;
    21       int id=0;
    22       while(i)
    23       {
    24           res[id++]=i%2;//哈夫曼编码
    25           i/=2;
    26       }
    27       for(i=id-1;i>=0;i--)
    28         printf("%d",res[i]);
    29       printf("\n");
    30    }
    31    return 0;
    32 }

转载于:https://www.cnblogs.com/sdau--codeants/p/3364244.html

[AJVnEj.png]: http://img0.tuicool.com/AJVnEj.png
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211228/15234450971542a297988012928bc8c0.png