4017 - 火炬

2008年北京奥运会，你想成为一名火炬手，经过层层选拔，终于到了最后一关，这一关是一道很难的题目：任意给定一个正整数N（N<=100000），求一个最小的正整数M，使得N×M的十进制表示形式里只含有1和0。

Input

一个正整数N。

Output

输出一行，如果有解，输出最小的M，否则输出“No Solution”。

Examples

Input

Output

Hint

【数据范围】
30%的数据保证答案不超过1000000。

Solution C++

#include<cstdio> 
#include<algorithm> 
using namespace std; 
#define F(x) for(int x=0;x<=1;x++) 
int n,i,j,k,l,m,o,p,q,w,e; 
long long ans=99999999999999999;
int main() 
{ 
    bool t=true; 
    scanf("%d",&n); 
    F(i) 
     F(j) 
      F(k) 
       F(l) 
        F(m) 
         F(e) 
          F(o) 
           F(p) 
            F(q) 
             F(w) 
              F(i1)
               F(i2)
                F(i3)
                 F(i4)
                  F(i5)
                   F(i6)
                    F(i7)
                     F(i8)
                      F(i9)
            { 
                long long temp=1*i+10*j+100*k+1000*l+10000*m+100000*e+1000000*o+10000000*p+100000000*q+1000000000*w;
				long long temp2=10000000000*i1+100000000000*i2+1000000000000*i3+10000000000000*i4+100000000000000*i5+1000000000000000*i6+10000000000000000*i7+100000000000000000*i8+1000000000000000000*i9;
				temp+=temp2;
                if(temp%n==0 and temp!=0) 
                { 
                    ans=min(ans,temp/n); 
                    t=false; 
                } 
            }      
    if(!t)    
    printf("%lld\n",ans); 
    else
    printf("No Solution\n");  
}

Hint

【数据范围】

30%的数据保证答案不超过1000000。

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题