Cod sursa(job #2073143)

Utilizator Stefan_RaduStefan Radu Stefan_Radu Data 22 noiembrie 2017 19:05:23
Problema Suma si numarul divizorilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream cin("ssnd.in");
ofstream cout("ssnd.out");
  
const int MAX_PR = 78507;
const int MAX = 1e6 + 7;

void Init(vector < long long > &prime) {

  int index = 0;
  vector < bool > used (MAX);
  for (int i = 2; i < MAX; i ++) {
    if (used[i]) {
      continue;
    }

    prime[++ index] = 1ll * i;
    for (int j = i + i; j < MAX; j += i) {
      used[j] = true;
    }
  }
}

void Print_ssnd(long long n, vector < long long > &prime) {

  long long d = 1ll, s = 1ll;
  for (int i = 1; prime[i] * prime[i] <= n; i ++) {
    if (n % prime[i]) {
      continue;
    }

    int cur_exp = 0;
    long long cur_nr = 1;
    while (n % prime[i] == 0) {
      n /= prime[i];
      cur_exp ++;
      cur_nr *= 1ll * prime[i];
    }

    d *= (cur_exp + 1);
    s *= ((cur_nr * prime[i] - 1) / (prime[i] - 1));
  }

  if (n != 1) {
    d *= 2ll;
    s *= ((n * n - 1) / (n - 1));
  }

  cout << d << ' ' << s << '\n';
}

int main(int argc, char const *argv[]) {
  
  vector < long long > prime(MAX);
  Init(prime);

  int t;
  cin >> t;
  while (t --) {

    long long n;
    cin >> n;
    Print_ssnd(n, prime);
  }
}