Divisibility Triples
National Olympiad — Municipal round (2022 season)
Submission name: threediv.cpp
Problem summary
Given N distinct positive integers in arbitrary order, count triples A<B<C from the set such that A divides B and B divides C.
Input
N, then N distinct positive integers.
Output
The number of divisibility triples.
Constraints
1 ≤ N ≤ 10^6; 1 ≤ ai ≤ 3000000.
Worked example
Official example, transcribed with whitespace restored from the PDF.
Input
7 2 1 3 10 7 30 6
Output
10
Solution analysis
- Choose the middle value B. Its contribution is the number of present proper divisors of B multiplied by the number of present proper multiples of B. The input order does not matter.
- Use a sieve over multiples. For every present d, visit 2d,3d,…; increase the proper-divisor count of each visited value, and count those visited values that are present. The latter is the proper-multiple count for d.
- Finally sum divisorCount[B]×multipleCount[B] over present B. In the sample, B=2 contributes three triples through multiples 6,10,30, while B=6 contributes two through the divisors 1 and 2 and multiple 30.
Why it works
Every valid triple has a unique middle value B. The sieve counts precisely the smaller present divisors and larger present multiples of B; each pair of such choices yields a valid triple and different pairs yield different triples. Summing the products therefore counts each valid triple exactly once.
Watch out. Exclude d itself by starting at 2d; store the final count in long long.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every valid triple has a unique middle value B. The sieve counts precisely the smaller
// present divisors and larger present multiples of B; each pair of such choices yields a valid triple
// and different pairs yield different triples.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>values(n);
int limit=0;
for(int&v:values){
cin>>v;
limit=max(limit,v);
}
vector<unsigned char>present(limit+1);
vector<int>divisors(limit+1),multiples(limit+1);
for(int v:values){
present[v]=1;
}
for(int d:values){
for(int v=d+d;v<=limit;v+=d){
++divisors[v];
multiples[d]+=present[v];
}
}
long long answer=0;
for(int b:values){
answer+=1LL*divisors[b]*multiples[b];
}
cout<<answer<<'\n';
}