Cuantos, C++ (gcc)

Cuantos

#include <iostream>
#include <map>
#include <vector>
#define MOD 700666007

using namespace std;

typedef long long ll;

map<int, int> periodo;
vector<ll> numeros, acumulado;

int getPeriodo(int a, int b){
    int i = 0, r;
    r = a%b;
    while(r!=0 and periodo.find(r) == periodo.end()) {
        periodo[r] = i;
        a = r*10;
        r = a%b;
        numeros.push_back(a/b);
        if(i == 0) acumulado.push_back(a/b);
        else acumulado.push_back((a/b + acumulado[i-1]%MOD)%MOD);
        i++;
    //cout<<"a/b: "<<a/b<<"\n";
    }
    return r;
}

int main(){
    int a, b, n, T;
    int r, indice, tamano, exc, vueltas;
    int cant_per, cant_exc, tam_per, per;
    
    
    cin>>T;
    while(T--){
    cin>>a>>b>>n;
    
    r = getPeriodo(a,b);
    indice = periodo[r];
    tamano = numeros.size();
    
    /*cout<<"numeros: ";
    for(auto a: numeros){
        cout<<a<<" ";
    }cout<<"\n";
    cout<<"\nacumulado: ";
    for(auto a: acumulado){
        cout<<a<<" ";
    }*/
                
    
    //cout<<"\nIndice: "<<numeros[indice]<<"\n";
    if (n <= tamano)
        cout<<acumulado[n-1]%MOD<<"\n";
        else if (n > tamano and r==0)
            cout<<acumulado[tamano-1]%MOD<<"\n"; 
            else {
                if (indice != 0) cant_per = (acumulado[tamano-1]%MOD-acumulado[indice-1]%MOD)%MOD;
                else cant_per = acumulado[tamano-1]%MOD;
                tam_per = tamano-indice;
                vueltas = (n-tamano)/tam_per;
                exc = n%tam_per;
            if(exc != 0) {
                if (indice != 0) cant_exc = (acumulado[indice + exc - 1]%MOD - acumulado [indice - 1]%MOD)%MOD;
                else cant_exc = acumulado[indice + exc - 1]%MOD;
            } else cant_exc = 0;
            // cout<<"cant: "<<acumulado[indice + exc - 1]<<"\n";
            // cout<<"tams: "<<cant_per <<" "<< vueltas*cant_per <<" "<< cant_exc<<"\n";
            cout<<(cant_per%MOD + vueltas*cant_per%MOD + cant_exc%MOD)%MOD<<"\n";
            }
    periodo.clear();
    numeros.clear();
    acumulado.clear();
    }
}


run \| edit \| history \| help	0