Cod sursa(job #2299599)

Utilizator AlexPascu007Pascu Ionut Alexandru AlexPascu007 Data 9 decembrie 2018 19:30:37
Problema Multiplu Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>
#include <bitset>
#include <vector>
#include <algorithm>
#define DIM 2000010
using namespace std;
ifstream fin("multiplu.in");
ofstream fout("multiplu.out");
long long a,b,i,j,k,p,q,m,d,ok,rest,f[DIM];
bitset<DIM> v;
int cmmdc(int a,int b) {
	if (b==0)
		return a;
	return cmmdc(b,a%b);
}
long long mod(bitset<DIM> A,long long x,long long cif) {
	long long r=0;
	for (i=cif;i>0;i--)
		r=(r*10+A[i])%x;
	return r;
}
int main() {
	fin>>a>>b;
	if (a*b==1) {
		fout<<"1";
		return 0;
	}
	d=cmmdc(a,b);
	m=a*b/d;
	ok=0;
	v[0]=1; v[1]=1; k=1;
	while (ok==0) {
		v[++k]=1;
		rest=mod(v,m,k);
		if (f[rest]==1) {
			q=k; ok=1;
			j=k; break; //nr1 o sa fie 111...11 - de j ori
		}
		else
			f[rest]=1;
	}
	k=0;
	for (i=1;i<=m;i++) {
		k++;
		if (mod(v,m,k)==rest) //nr2 o sa fie 111...11 - de i ori
			break;
	}
	p=k;
	for (int l=1;l<=p;l++)
		v[l]=0;
	for (i=q;i>=1;i--)
		fout<<v[i];
	return 0;
}