Pagini recente » Cod sursa (job #2578289) | Cod sursa (job #663119) | Cod sursa (job #963717) | Cod sursa (job #2775142) | Cod sursa (job #115219)
Cod sursa(job #115219)
#include <stdio.h>
#define maxN 2000100
int a,b,n;
int vec[maxN],lst[maxN],st,cur,k;
int gcd(int a,int b){int c;do{if(a<b)c=a,a=b,b=c;a%=b;}while(a);return b;}
void inputFunc(){FILE*fi=fopen("multiplu.in","r");fscanf(fi,"%d %d",&a,&b);n=a*b/gcd(a,b);fclose(fi);}
void outputFunc(){
FILE*fi=fopen("multiplu.out","w");
int x=0,ul=vec[x];
while(x!=-1){
for(int i=ul;ul>vec[x];ul--)fprintf(fi,"0");
fprintf(fi,"1");ul--;
x=lst[x];
}
while(ul--)fprintf(fi,"0");
fclose(fi);
}
int main(){
inputFunc();
vec[1]=1;lst[1]=-1;
k=2;
cur=st=10%n;
for(;!vec[0];cur=(cur*st)%n,k++){
for(int i=n-1;i>0;i--)if(vec[i] && vec[i]<k){
int u=i+cur;if(u>=n)u-=n;
if(!vec[u])vec[u]=k,lst[u]=i;
}
if(!vec[cur])vec[cur]=k,lst[cur]=-1;
}
outputFunc();
return 0;
}