Cod sursa(job #123870)

Utilizator bogdanhm999Casu-Pop Bogdan bogdanhm999 Data 17 ianuarie 2008 16:41:53
Problema Multiplu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
//111 101 000 010 010 000 000
// 18 446 744 073 709 551 616

#include <stdio.h>
bool rest[2000000];
long A,B,cmmmc,i,r,p,m,nr;

int main(){
    freopen("multiplu.in","r",stdin);
    freopen("multiplu.out","w",stdout);
    
    scanf("%ld %ld",&A,&B);
    
    cmmmc=A*B;
    while (A!=B)
          if (A>B){
             A=A%B;
             if (A==0)A==B;
          }
          else{
               B=B%A;
               if (B==0)B=A;
          }
    cmmmc/=A;
    rest[0]=0;
    for (m=1;m<=2000002;m++){
        r=0;
        p=0;
        while (1<<(p+1)<=m)p++;
        for (;p>=0;p--){
             r*=10;
             r+=(m&(1<<p))/(1<<p);
             r=r%cmmmc;
        }
        if (r==0){nr=m;break;}
        if (rest[r]){nr=m-rest[r];break;}
        else rest[r]=m;
    }
    p=0;
    while (1<<(p+1)<=nr)p++;
    for (i=p;i>=0;i--)
        printf("%ld",(long)(nr&(1<<i))/(1<<i));
        
    return 0;
}