Ticks from Digits and Prime Factors
National Olympiad — National round (2026 season)
Submission name: cak.cpp
Problem summary
For integers 1…n, separately count occurrences of decimal digits 5 or 7 and occurrences of prime factors 5 or 7 with multiplicity. Print both exact totals.
Input
One positive decimal integer n.
Output
The decimal-digit tick total and the prime-factor tick total.
Constraints
1 ≤ n ≤ 10^5000, so the input may contain 5001 decimal digits.
Worked example
Input and output for the worked example discussed below.
Input
17
Output
4 5
Solution analysis
- The two counts are different. Up to 17 the decimal ticks occur in 5,7,15,17, giving 4. Prime-factor ticks occur in 5,7,10,14,15, giving 5. Repeated factors count repeatedly, for example 75 contains two factors of 5.
- Compute decimal ticks using digit DP over the bound. smallerWays counts prefixes already below the matching prefix of n; smallerTicks counts all their ticks. tightTicks counts ticks in the one prefix still equal to n. Leading zeros contribute nothing, so counting zero-padded numbers from 0 through n is safe.
- When the next bound digit is d, old smaller prefixes contribute 10×smallerTicks inherited ticks plus 2×smallerWays new ticks. The d newly-smaller continuations of the tight prefix add d×tightTicks+[d>5]+[d>7]. Update smallerWays to 10×smallerWays+d, and extend tightTicks if d is 5 or 7. At the end add tightTicks to include n.
- For a prime p, count one factor from multiples of p, another from multiples of p², and so on. The total exponent is floor(n/p)+floor(n/p²)+… . Repeatedly divide a copy of n by 5 and add the quotients; repeat for 7.
- BigInteger stores little-endian base-10^9 limbs. Addition, multiplication by a small integer, division by a small integer, and decimal printing suffice. No floating-point powers or general big-integer multiplication are needed. Printing each lower limb with nine digits preserves internal zeros.
Why it works
The digit transition partitions all prefixes into already-smaller and exactly-equal cases, accounting for each allowed continuation and each old/new tick exactly once. Induction gives the decimal total over [0,n], where zero contributes zero. A number divisible by p^e contributes to exactly e of the prime-power divisibility layers, so the quotient sum gives its prime factors with the required multiplicity.
Watch out. Do not convert n to a built-in integer or use floating-point approximations. Include n. Keep the totals separate. Count multiplicity in factorization and pad lower big-integer limbs during printing.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<cstdint>
#include<iomanip>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
using namespace std;
class BigInteger{
static const uint64_t base=1000000000;
vector<uint32_t>digits;
public:
BigInteger(uint32_t value=0):digits(1,value){
}
bool isZero()const{
return digits.size()==1&&digits[0]==0;
}
void multiplySmall(uint32_t factor){
uint64_t carry=0;
for(uint32_t&digit:digits){
uint64_t value=uint64_t(digit)*factor+carry;
digit=value%base;
carry=value/base;
}
if(carry!=0){
digits.push_back(carry);
}
}
void add(const BigInteger&other){
digits.resize(max(digits.size(),other.digits.size()),0);
uint64_t carry=0;
for(size_t i=0;i<digits.size();i++){
uint64_t value=uint64_t(digits[i])+carry;
if(i<other.digits.size()){
value+=other.digits[i];
}
digits[i]=value%base;
carry=value/base;
}
if(carry!=0){
digits.push_back(carry);
}
}
void divideSmall(uint32_t divisor){
uint64_t remainder=0;
for(int i=int(digits.size())-1;i>=0;i--){
uint64_t value=remainder*base+digits[i];
digits[i]=value/divisor;
remainder=value%divisor;
}
while(digits.size()>1&&digits.back()==0){
digits.pop_back();
}
}
string toString()const{
ostringstream output;
output<<digits.back();
for(int i=int(digits.size())-2;i>=0;i--){
output<<setw(9)<<setfill('0')<<digits[i];
}
return output.str();
}
};
BigInteger exponentSum(BigInteger number,int prime){
BigInteger total;
while(!number.isZero()){
number.divideSmall(prime);
total.add(number);
}
return total;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string bound;
cin>>bound;
BigInteger number;
BigInteger smallerWays;
BigInteger smallerTicks;
int tightTicks=0;
for(char character:bound){
int digit=character-'0';
// Extend old smaller prefixes, then count prefixes newly below the bound.
smallerTicks.multiplySmall(10);
BigInteger added=smallerWays;
added.multiplySmall(2);
smallerTicks.add(added);
smallerTicks.add(BigInteger(tightTicks*digit+(digit>5)+(digit>7)));
smallerWays.multiplySmall(10);
smallerWays.add(BigInteger(digit));
tightTicks+=digit==5||digit==7;
number.multiplySmall(10);
number.add(BigInteger(digit));
}
smallerTicks.add(BigInteger(tightTicks));
BigInteger factorTicks=exponentSum(number,5);
factorTicks.add(exponentSum(number,7));
cout<<smallerTicks.toString()<<' '<<factorTicks.toString()<<'\n';
return 0;
}