Cod sursa(job #2766638)

Utilizator BlueLuca888Girbovan Robert Luca BlueLuca888 Data 2 august 2021 16:36:10
Problema Suma si numarul divizorilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#define MOD 9973

using namespace std;

ifstream fin ("ssnd.in");
ofstream fout ("ssnd.out");

bitset <1000001> v;

int t, pp, p[80000], ii, e;
unsigned long long n, nrd, sumd, x;

int main (){

      v[0]=1;
      v[1]=1;
      for(int i=2; i*i<=1000000; i++)
            if(v[i] == 0){

                  for(int j=i*i; j<=1000000; j+=i)
                        v[j]=1;
            }

      for(int i=2; i<=1000000; i++)
            if(v[i] == 0){
                  pp++;
                  p[pp]=i;
            }

      fin>>t;

      for(int pas=1; pas<=t; pas++){

            fin>>n;
            ii=1;
            nrd=1;
            sumd=1;

            while(p[ii] <= n/p[ii] && n != 1 && ii <= pp){
                  e=0;
                  while(n%p[ii] == 0){
                        e++;
                        n=n/p[ii];
                  }

                  if(e == 0){
                        ii++;
                        continue;
                  }

                  nrd=nrd * (e+1);

                  x=pow(p[ii], e+1);
                  sumd*=((x-1)/ (p[ii]-1));
                  sumd=sumd %MOD;

                  ii++;
            }

            if(n != 1){
                  sumd*=((n*n -1)/(n-1))%MOD;
                  sumd=sumd%MOD;
                  nrd*=2;
            }

            fout<<nrd<<" "<<sumd<<"\n";
      }

      return 0;
}