Cod sursa(job #2664141)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 28 octombrie 2020 00:06:01
Problema Suma si numarul divizorilor Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <bitset>
using namespace std;

#define MAX 1000003
#define MOD 9973

bitset<MAX> er;
int primes[MAX];
int primesno;

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


inline void erathostenes() {
    primesno = 1;
    primes[1] = 2;
	for(int i=3;i<MAX; i +=2)
		if (! er[i]) {
			++primesno;
			primes[primesno] = i;

			for(int j=i + i; j<MAX; j+= i)
				er[i] = 1;
		}
}


inline int pow(int x, int p) {
	int res = 1;
	while(p) {
		if (p & 1) {
			res *= x;
			res %= MOD;
		}

		x *= x;
		x %= MOD;
		p >>= 1;
	}
	return res;
}

int main() {
	int n;
	long long x, sum;
	int num, divno;
	fin >> n;

	erathostenes();
	for(int j=1; j<=n; ++j) {
		fin >> x;
		sum = 1;
        num = 1;
        divno = 0;

        for(int i=1; i <= primesno && 1LL*primes[i]*primes[i] <=x; ++i)
            if (x % primes[i] == 0) {
                divno = 0;
                while(x % primes[i] == 0) {
                    x /= primes[i];
                    ++divno;
                }

                num *= divno + 1;
                sum = sum * (pow(primes[i], divno + 1) - 1) * pow(primes[i] - 1, MOD - 2) % MOD;
            }

        if (x > 1) {
            num <<= 1;
            sum = sum * (x + 1) % MOD;
        }
        fout << num << " " << sum << "\n";
	}

	return 0;
}