|
|
Страница 4 #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. Страница 3 I have WA on test 7. What i need to do? 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? ---- 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. #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? assc Edited by author 20.03.2019 19:54 Use long long Not work. Can i give my code? [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. #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? For those who using prime numbers! Search biggest prime number that <= max!!! NOT first prime number that >=min !! 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:42 First you should rewrite function which counts sum of divisors: for (i=2;i*i<=n;i++)..., second you shouldn't compute triviality of all numbers in [i,j]: just for numbers from j downto first prime number>=i, and of course take into account that triviality(1)=0. WHAT IS TEST 8 the right border is a Prime number I have 9 times WA#9 and all becouse I don't use double... If you have WA#9, use double in computing triliality, and get AC =) Good Luck! Паскаль почти все задачи по лимиту не проходят на одно и то же время, почему??? Страницы: 4 3 2 1 Предыдущая |
|
|