P2841 A*B Problem

admin

https://www.luogu.org/problemnew/show/P2841

题目描述
给出一个数A，你需要给出一个最小的数B，使得A与B的乘积只含有0和1

输入输出格式
输入格式：
一个正整数A

输出格式：
正整数B和A与B的乘积，两数之间用一个空格隔开

输入输出样例
输入样例#1：
6
输出样例#1：
185 1110
样例说明：6*185=1110
//只输出第一行即可，无需输出样例说明
说明
对于30%的数据，0<N<20

对于50%的数据，0<N<100

对于70%的数据，0<N<1000

对于100%的数据，0<N<10000

黄煦喆

80分 最后2个点好像要用高精度

1. #include<iostream>
   
2. #include<queue>
   
3. using namespace std;
   
4. typedef unsigned long long ull;
   
5. ull a,s,b;
   
6. queue<ull>pq;
   
7. int main()
   
8. {
   
9.     cin>>a;
   
10.     pq.push(1);
    
11.     while(!pq.empty()&&!b)
    
12.     {
    
13.         s=pq.front();
    
14.         pq.pop();
    
15.         if(!(s%a))b=s/a;
    
16.         else
    
17.         {
    
18.             pq.push(s*10);
    
19.             pq.push(s*10+1);
    
20.         }
    
21.     }
    
22.     cout<<b<<' '<<s;
    
23.     return 0;
    
24. }
    

复制代码