Sleeping in Class - Help with Proof

How do you find the maximum amount of factors under 1e6?

And why is this problem in Bronze?
Problem:
http://usaco.org/index.php?page=viewproblem2&cpid=1203
Solution:
http://usaco.org/current/data/sol_prob1_bronze_feb22.html

It will definitely be at most 2\cdot \sqrt{10^6}=2\cdot 10^3. If you want to compute the answer exactly that’s also not too hard:

#include <bits/stdc++.h>
using namespace std;

int main() {
	vector<int> num_divisors(1e6+1);
	for (int i = 1; i < size(num_divisors); ++i) {
		for (int j = i; j < size(num_divisors); j += i) {
			++num_divisors[j];
		}
	}
	int ans = 0;
	for (int x: num_divisors) ans = max(ans,x);
	cout << ans << "\n"; // 240
}

or see A066150 - OEIS

Why not?

2 Likes

I just think the (10^6-240) + 240 x 10^5 or (10^3+1-240) + 240 x 10^5 (I think this is the minimized complexity???) is a little hard for bronze but I don’t know.

May I ask if it’s true that the problems are getting harder? It seems that way to me this year.

Also, I might be asking much, but since you have a strong math background, may I ask how you would compute the largest amount of factors between a given range without coding it? Like is there any trick? Thanks

Sorry, last question, why did you do 2 x 10^3, I thought it was up to 10^3

What should it be in, then? Also, does this require anything outside of the bronze concepts?

1 Like

I don’t understand this at all. Could you explain what you mean more clearly?

“Harder” is subjective. It won’t be hard if you improve your coding and most importantly your thinking skills.

There are at most 2 \sqrt{N} factors of N

The upper bound is clearly 2 \sqrt{N} factors.

What I mean is that the complexity just seems a little weird to me but idk.

Btw I don’t know if I did the complexity correctly, I just assumed there were 10^6 operations, in which 240 of them consisted of 1e5 operations, and sorry, ignore the second part, I got mixed up

I was not asking a question relevant to the problem, I was just curious if it is possible to use just math to find the max factors in a given range, just through pen and paper

I’m not aware of an (easy) way to get a better bound than 2\sqrt N through pen and paper.