Sleeping in Class - Help with Proof

Problems and Contests
#1

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

#2

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
#3

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.

#4

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

#5

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

#6

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

#7

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

#8

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

#9

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

#10

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

#11

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

#12

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

#13

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

#14

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