abc_Bunget_macelarit

#include <cstdio>
#define BAZA 1000000
#define Nmax 100000
using namespace std;

int main()
{
    int a,b;
    scanf("%d %d",&a,&b); /// Citesc datele de intrare a si b
    int c=a*b;
    int copie_c=c,repr_binar_a_lui_c[22]; /// repr_binar_a_lui_c va memora reprezentarea binara a lui c=axb
    while(copie_c!=0)
        repr_binar_a_lui_c[++repr_binar_a_lui_c[0]]=copie_c%2,copie_c=copie_c/2;
    int i,j,doi_la_a_minus_1=1;
    for(i=1;i<=a;++i) /// Calculez 2^a
        doi_la_a_minus_1=doi_la_a_minus_1*2;
    --doi_la_a_minus_1; /// Scad 1 si obtin 2^a-1
    int d; /// Memoreaza cel mai mic divizor al lui 2^a-1
    long long p1;
    for(i=2;i<=doi_la_a_minus_1;++i) /// Calculez primul divizor d al lui 2^a-1
    {
        p1=1;
        for(j=repr_binar_a_lui_c[0];j>=1;--j)
            if(repr_binar_a_lui_c[j]==0 )
                p1=(p1*p1)%i;
            else
                p1=(p1*p1*2)%i;
        if(p1==1)
            {
                d=i;
                break;
            }
    }
    int r=c%15; /// 2^15=32768
    int doi_la_r=1 ;
    for(i=1;i<=r;++i) /// Calculez 2^r
        doi_la_r=doi_la_r*2;
    int n=c/15;
    long long A[Nmax]; /// Numarul A=2^(axb)-1
    A[0]=1; /// Memoreaza numarul de cifre ale lui A in baza BAZA
    A[1]=1; /// La inceput A=1
    long long t,t1; /// Transportul t
    for(i=1;i<=n;++i) /// Calculez A=2^c (pentru ca inmultesc cu 32768, iar c=n*15)
    {
        t=0;
        for(j=1;j<=A[0];++j) /// ? Calculez produsele intermediare, impreuna cu suma intermediara
        {
            t1=(A[j]*32768+t)%BAZA;
            t=(A[j]*32768+t)/BAZA;
            A[j]=t1 ;
        }
        if(t>0)
            A[++A[0]]=t;
    }
    t=0;
    for(j=1;j<=A[0];++j) /// ? Corectez sumele intermediare
    {
        t1=(A[j]*doi_la_r+t)%BAZA;
        t=(A[j]*doi_la_r+t)/BAZA;
        A[j]=t1;
    }
    if(t>0) /// Daca ultimul transport e mai mare decat 0, il "adaug" la rezultat
        A[++A[0]]=t;
    i=1;
    while(A[i]==0)
        ++i;
    --A[i];
    t=0;
    for(i=A[0];i>=1;--i) /// Calculez A/d (divizorul propriu maxim)
    {
        t1=(t*BAZA+A[i])/d;
        t=(t*BAZA+A[i])%d;
        A[i]=t1;
    }
    while(A[A[0]]==0)
        --A[0];
    printf("%ld",A[A[0]]); /// Afisez rezultatul (prima valoare fara zerouri nesemnificative)
    for(i=A[0]-1;i>=1;--i)
        printf("%06ld",A[i]); /// iar restul valorilor le completez cu zerouri in fata
    return 0;
}