Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

排列组合的要给tong long, 给int会因为溢出导致WA

Posted by SmartChen at 2018-11-08 23:23:30 on Problem 3421 and last updated at 2018-11-08 23:29:50
#include <iostream>
#include <stdio.h>

#define MAX 1048580
#define PLEN 85000
using namespace std;

bool isprime[MAX];
int prime[PLEN];
int i, j, X;

int main()
{
//prime
fill(isprime, isprime + MAX, true);
isprime[0] = false;
isprime[1] = false;
int sum = 0;
for (i = 2; i < MAX; i++) {
if(isprime[i]) {
prime[sum++] = i;
for (j = i + i; j < MAX; j += i)
isprime[j] = false;
}
}

while (scanf("%d", &X) == 1) {
if (isprime[X]) {
printf("1 1\n");
continue;
}

int index = 0, ans = 0;
long long A = 1;
//decomposite prime factors
{
while (X > 1) {
int mod = prime[index++];
int cnt = 1;
while (X % mod == 0) {
ans++;
X /= mod;
A *= cnt++;
}
}
}

//pow, permutation and combination
long long pow = 1;
for (j = 2; j <= ans; j++){
pow *= j;
}
pow /= A;
printf("%d %lld\n", ans, pow);
}
return 0;
}

Followed by: