Counting Unitary Divisors
National Olympiad — National round (2026 season)
Submission name: divs.cpp
Problem summary
A divisor d of n is unitary when gcd(d,n/d)=1. Answer many queries asking for the number of unitary divisors.
Input
q followed by q values n.
Output
q answers separated by spaces on one line.
Constraints
1 ≤ q ≤ 10^6; 1 ≤ n ≤ 10^6.
Worked example
Input and output for the worked example discussed below.
Input
3 4 3 200
Output
2 2 4
Solution analysis
- Factor n into its k distinct prime-power blocks. A prime cannot occur in both d and n/d, otherwise their gcd would exceed 1. Hence a whole block p^e must go into d or into n/d, with no splitting.
- Each block gives two independent choices, so there are 2^k unitary divisors. For 4=2², d=2 is not unitary; only 1 and 4 qualify. For 200=2³×5², choose neither, either, or both blocks to get 1,8,25,200.
- Precompute k for every integer up to one million. Initially all entries are zero. A p≥2 still having zero factors is prime because any composite would have been visited by a smaller prime. Increment every multiple of p once.
- After the sieve each query is a single lookup and a power of two, written as 1 shifted left by k. The value 1 has k=0 and answer 1. A byte is sufficient for the factor counts; the sieve avoids repeating factorizations for up to a million queries.
Why it works
Unitary divisors are in bijection with subsets of the distinct prime-power blocks: splitting a block violates coprimality, and any whole-block subset is coprime to its complement. The sieve counts each distinct prime divisor once, so returning 2^k is exact.
Watch out. Do not count prime factors with multiplicity or use the ordinary-divisor formula ∏(e+1). Remember n=1. Do not store a million queries when they can be streamed.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int limit=1000000;
vector<unsigned char>factors(limit+1,0);
for(int prime=2;prime<=limit;prime++){
if(factors[prime]==0){
// Each prime contributes one independent prime-power block.
for(int multiple=prime;multiple<=limit;multiple+=prime){
factors[multiple]++;
}
}
}
int q;
cin>>q;
for(int i=0;i<q;i++){
int number;
cin>>number;
if(i>0){
cout<<' ';
}
cout<<(1<<factors[number]);
}
cout<<'\n';
return 0;
}