Pagini recente » Cod sursa (job #1174416) | Cod sursa (job #1378348) | Cod sursa (job #860929) | Cod sursa (job #2042587) | Cod sursa (job #1832203)
#include <stdio.h>
#include <string.h>
#define MOD 9973
int primes[78498] = {2};
int k = 0;
int PrimeNumbersSieve5(int N){
int i, j, primeNumbers = 1;
char list[2000005]; memset(list, 0, 2000005);
for(i = 1; ((i * i) << 1) + (i << 1) <= N; i += 1){
if((list[i >> 3] & (1 << (i & 7))) == 0){
for(j = ((i * i) << 1) + (i << 1); (j << 1) + 1 <= N; j += (i << 1) + 1){
list[j >> 3] |= (1 << (j & 7));
}
}
}
for (i = 1; 2 * i + 1 <= N; ++i){
if((list[i >> 3] & (1 << (i & 7))) == 0){
primes[++k] = 2 * i + 1;
primeNumbers++;
}
}
return primeNumbers;
}
unsigned long long expo(unsigned long long a, unsigned long long b){
unsigned long long result = 1;
while (b){
if (b&1){
result = (result * a);
}
b >>= 1;
a = (a * a);
}
return result;
}
int main(){
FILE *file1, *file2;
unsigned long long T, M, N, i, Sum, nDiv, power;
file1 = fopen("ssnd.in", "r");
file2 = fopen("ssnd.out", "w");
PrimeNumbersSieve5(1000000);
fscanf(file1, "%llu", &T);
while(T--){
nDiv = 1;
Sum = 1;
fscanf(file1, "%llu", &N);
M = N;
for(i=0; primes[i]<=N/2; i++){
power = 0;
if(!(M%primes[i])){
while(M%primes[i]==0){
M /= primes[i];
power++;
}
nDiv *= (power + 1);
Sum = (Sum * ((expo(primes[i], power+1) - 1) / (primes[i] - 1))%MOD) % MOD;
}
if(M==1){
break;
}
}
if(nDiv==1 && Sum==1 && N!=1){
nDiv = 2;
Sum += N;
}
fprintf(file2, "%llu %llu\n", nDiv, Sum);
}
return 0;
}