#include <iostream> #include <limits> #include <cmath> bool isPrime(int n) { if (n <= 1) { return false; }
for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } }
return true; } int lowest_trivia_number (int I, int J) { double min_trivia = std::numeric_limits<double>::max(); int res = 0; for (int i = I; i <= J; i++) { int sum_of_own_denominators = 1; for(int j = 2; j <= std::sqrt(i); j++){ if(i % j == 0) { sum_of_own_denominators += j; if(j != i / j) { sum_of_own_denominators += i / j; } } } double cur_trivia = sum_of_own_denominators/i; if (cur_trivia < min_trivia) { min_trivia = cur_trivia; res = i; } } return res; } int main() { int I, J;
std::cin >> I >> J; if(I == 1) { std::cout << 1; return 0; } int largestPrime = -1; for (int num = J; num >= I; num--) { if (isPrime(num)) { largestPrime = num; break; } } if (largestPrime != -1) { std::cout << largestPrime << std::endl; } else { std::cout << lowest_trivia_number(I, J); } return 0; } If you look at the statement, it says "Triviality of a natural number N is the ratio of the sum of all its proper divisors to the number itself. Recall that a proper divisor of a natural number is the divisor that is strictly less than the number.". Therefore, triviality of 1 should be 0 / 1 == 0, since 1 doesn't have any divisor strictly less than itself. However, I couldn't get an AC (WA4) until I changed the line if (I == 1) ans = 0 to if (I == 1) ans = 1. So, either the statement or the tests are broken. Edited by author 05.08.2022 19:55 Edited by author 05.08.2022 19:55 I'm not an admin. You must write the number with minimal triviality. Triviality(1) == 0, that means you have to print 1 because 1 is number with minimal triviality. But you try to print the triviality of 1(i.e. 0). The statement is correct. I have WA on test 7. What i need to do? Output is EndPoint. EndPoint is simple. Use long long Not work. Can i give my code? What is test 5? I can give my code(It's not working), runtime error(access violation) Good afternoon! I am a programmer-beginner. I have written the code for this task on c++, but the time limit is exceeded on the second test! The code is this: ( https://ideone.com/Rh98zQ) #include <iostream> using namespace std; float ghj(int a) {int m; m=0; for(int l=1; l<a; l++) {if(a%l==0) {m=m+l;}} float c=(float(int(m))); float b=c/a; return b;} int main() { int i,j; cin >> i >> j; float p=ghj(i); int n=i; for(int o=i; o<=j; o++) {if(ghj(o)<p) {p=ghj(o); n=o;}} cout << n; return 0; } Tell me, please, how can I optimize the code? #include <iostream> using namespace std; int main() { long long i, j, iDel; long long biggestV = 9999999, biggestDel = 9999999; cin >> i >> j; if (i == 1) { cout << 1; return 0; } else if (i == j) { cout << i; return 0; } else if (i + 1 == j) { cout << (j % 2 != 0 ? j : i); return 0; } for (long long iV = j % 2 != 0 ? j : j-1; iV >= i; iV -= 2) { for (iDel = j / 3 + 1; iDel >= 1; iDel--) { if (iV%iDel == 0) { if (iDel < biggestDel) { biggestDel = iDel; biggestV = iV; } break; } } if (iDel == 1) { cout << iV; return 0; } } cout << biggestV; } In the main cycle you doesn't compare trivialities, you search the smallest biggest divisor in the weird range instead. Could you please show the mathematical proof of your main cycle? Edited by author 31.03.2020 14:11 Edited by author 31.03.2020 14:12 Hi.Did you solve this problem? ---- ll l,r; cin >> l >> r; if(l==1){ cout << 1; return 0; } if(l == r){ cout << l; return 0; } ll n = 1e6+2; vector<bool> prime(n+1,1); prime[0]=prime[1] = 0; for( ll i =2; i*i <= n; i++) { if(prime[i]) { for(ll j = i*i; j <= n; j+=i) prime[j]=0; } } for(ll i = r; i >= l; i--){ if(prime[i]) { cout << i; return 0; } } double mx =1e11; ll ans = 0; for(ll i = r; i >= l; i--){ if(i % 2 == 0) continue; double suma = 1; for(ll k = 2; k*k <= i; k++){ if( i % k == 0 ){ suma += k; if(i/k != k){ suma += (i/k); } } } double q=(suma)/(i); if( q < mx){ mx = q; ans = i; } } cout << ans; return 0; ---- I used the sieve of Eratosthenes to find prime numbers. If I have not found prime numbers on the interval [l; r], then I iterate over all numbers with [l; r]. I go through the divisors (sqrt (i)). I calculate the minimum. What's wrong? WA 11. Google translator, sorry. WHAT IS TEST 8 the right border is a Prime number Judjes tell me after you read my message, I will delete an AC program.
Here is th 1st program it got WA#3: [Program was deleted by author, beacuse it got AC =)] [Thx Vladimir! Judges if you need it, I can post it.] Here is 2nd program it got AC: [Program was deleted by author] [Judges if you need it, I can post that code for a while] Here is one test: 318 330 Correct answer is 323 (Triviality(323)=0.114551) AC programs answer for this tests was : 324 (Triviality(324)=1.619195) It means that AC program gave incorrect answer, but program which got WA#3 gave correct answer!!! It's shameful!!! Edited by author 20.01.2006 20:49 Edited by author 21.01.2006 02:45 What can you say about program which got wa? How can you make it to get AC? Your mistake is that you forget to add line prime:=true; in the end of prime(x) function I got AC!!! Vladimir, Thank you very much! You are genius! Большое человеческое спасибо! My code: [code deleted] I have Time limit exceeded. I need optimal solution of this task. Help me please! Edited by moderator 19.11.2019 23:40 go to the sqrt(b), not to b/2 > go to the sqrt(b), not to b/2 could you help understanding why? for 20 the triviality is `(1+2+4+5+10)/20`, kind of meaning you would need to go to b/2. no? gotcha. you can do (i + N/i), so the N/i bit will make sure you would need to go only up to sqrt(N). thanks assc Edited by author 20.03.2019 19:54 My code gives true answers for all tests but when I send problem it gives WA in test 3. please write answer. test 3 is nothing, but 2 1000000. So how should the answer look like? Is it the biggest possible prime number? you are right, just prime number [code deleted] Edited by moderator 19.11.2019 23:40 Hi, Very good solution! Just one note, it doesn't affect AC, but: In D+=(i+N/i); if (i == N/i) you don't need to add both i and N/i, but just i. In this case result of check(N) will be 100% equal to triviality(N) in all cases. I always get WA on test 4,who can give me the testdata of test4.Help me!Thank you. Triviality(1)=0 Thank's for help! You're completely right! AC now! Thanks.I got AC now. Of course I have same bugs. AC now I also have the same mistake.thanx a lot. Thank you very much!!!!!!! It is a very good advice! Thank you for your advice. I've gotten AC now.I wrote "1" if i=1. а как выглядит второе число? ведь тест - 2 числа, через пробел. Can you tell how look test4? the first is one, and the second is ..? Triviality(1) = 1 Triviality(1)=0 Edited by author 17.09.2015 23:28 Edited by author 17.09.2015 23:28#include <iostream> using namespace std; bool prime(long long n); int main() { long long a,odd, i, j, nice,b; cin >> a >> b; nice=0; if (a%2==1) {odd=a;} else {odd=a+1;} for (i=b; i>a; i--) { if (prime(i)) { nice=i; break; } } if ((a==1 or nice==0) and b!=a) { cout << odd;} else if (b==a) {cout << a;} else if (nice) {cout << nice << endl;} return 0; } bool prime(long long n) { bool w; w=n==2; if (!w and n%2) { w=1; for (int i=3; i*i<=n; i+=2) { if (n%i==0) { w=0 ; break; } } } if (w) { return 1; } else return 0; } Case "no prime is found" is suspicious. You think answer is the minimal odd number in the interval. Could you prove it? Why not maximal odd number in the interval? Why you don't want to do try brute force? Calculates sum of divisors. O(lim * log(lim)). for(int i = 2; i <= lim; ++i){ ++s[i]; for(int j = i + i; j <= lim; j += i) s[j] += i; } Maybe I don't understand it clear, but I think it will get TL. Difficult of this algorithm = O(n^2) No, it's O(n log n). Learn some math. [code deleted] Edited by moderator 19.11.2019 23:41 nuuu.. che skazat nu krasavchik. thanks you , my pro is TLE :) First, triviality of 1 is 0. Second, we can judge number i from 2 to 1000000, if i is a prime number, then prime[i] is true. Third, we traversal i from b to a, because if j>i and prime[j]==true, prime[i]==true, we can get 1/j<1/i. if we get prime[i]==true,just output it and break. if we can not get such a number, calculate triviality of i and output the minimum. Thus, we can get AC with a little time spended,but larger memory. My English is poor, if you cannot understand me, I would say sorry for it.^__^ your english are good) i got it. may be i got it because my solution is similar yours=) Your english good enouth to speak with Russians) |
|