Last Digit of a Product’s Divisor Count
National Olympiad — National round (2010 season)
Submission name: last.cpp
Problem summary
Find the final decimal digit of the number of positive divisors of the product of n given integers, without constructing that product.
Input
n followed by n positive integers.
Output
One digit: the divisor count modulo 10.
Constraints
1 ≤ n ≤ 20; 1 ≤ a[i] ≤ 10000.
Worked example
Input and output for the worked example discussed below.
Input
4 3 5 7 720
Output
0
Solution analysis
- Factor every input separately and add exponents of equal primes. Multiplying integers adds their prime exponents, so this gives the factorization of the enormous product without storing it.
- If prime p has total exponent e, a divisor chooses p^0 through p^e, giving e+1 possibilities. Independent prime choices multiply; keep that product modulo 10 after each factor.
- For 3×5×7×720 = 2^4×3^3×5^2×7, the divisor count is 5×4×3×2=120, whose last digit is 0. Inputs equal to 1 contribute no prime exponents.
Why it works
Unique prime factorization makes every divisor correspond bijectively to an independent exponent choice for each prime. Summing exponents across factors and multiplying their choice counts therefore computes the correct divisor count; modular multiplication preserves its final digit.
Watch out. Do not multiply all inputs first. Include 1 and the product among divisors. A leftover factor greater than 1 after trial division is prime.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int count;
cin>>count;
vector<int>exponent(10001,0);
for(int index=0;index<count;index++){
int value;
cin>>value;
for(int prime=2;prime*prime<=value;prime++){
while(value%prime==0){
exponent[prime]++;
value/=prime;
}
}
if(value>1){
exponent[value]++;
}
}
int answer=1;
// A divisor independently chooses one exponent for each prime.
for(int power:exponent){
answer=answer*(power+1)%10;
}
cout<<answer<<'\n';
}