Project Euler - 29. problem nasıl çözülür?

brkdnmz dedi:

a^b ve c^d kuvvetleri birbirine eşitse a ve c sayıları bire bir aynı asal çarpanları barındırır. Daha da ötesi, öyle bir x sayısı vardır ki a da c de x'in birer kuvvetidir. Sıkmamak için bunun kanıtına değinmeyeyim ama asal çarpanları ayrı ayrı düşünerek bir yerlere varabilirsiniz. Yine de isterseniz açıklamaya çalışırım.

a'nın aralığındaki -problemde [2, 100]- her sayı için en küçük x'i bulup onu kullanabiliriz. Birkaç örnek şu şekilde:

• 25 için x = 5 çünkü 5^2 = 25.
• 81 için x = 3 çünkü 3^4 = 81. 9 veya 81'i almıyoruz çünkü en küçük 3.
• 7 için x = 7.

Ben bu x'e "maske" ismini veriyorum. Bir sayının maskesi, bir kuvveti o sayıya eşit olan en küçük pozitif sayı oluyor.

Nasıl kullanabileceğimize gelirsek kuvvetleri hafızada existing_powers dizisinde tutabiliriz ama direkt gerçek değerlerini tutmayacağız. Bu dizinin her elemanı bir set olup problemin sınırları dahilindeki tüm kuvvetler için maskelerin var olan tüm üslerini tutacak. a'nın maskesi x ise ve x^k = a ise existing_powers[x]'e b'nin aralığındaki her t sayısı için -problemde [2, 100]- k * t sayılarını ekleriz.

Bu yaklaşım sayesinde büyük sayılarla uğraşmaya gerek kalmıyor. Çözümün C++ kodunu paylaşayım:

C++:

#include <bits/stdc++.h>

using namespace std;

/*
 n = a^k
 En küçük a > 0 için {a, k} döndürüyor.
*/
array<int, 2> get_mask(int n) {
 int init_n = n;
 vector<array<int, 2>> factorization;
 int g = 0;
 for (int i = 2; i * i <= n; i++) {
 if (n % i)
 continue;
 int exp = 0;
 while (n % i == 0)
 n /= i, exp++;
 factorization.push_back({i, exp});
 g = __gcd(g, exp);
 }

 if (n > 1) {
 return {init_n, 1};
 }

 int mask = 1;
 for (auto &[prime, exp] : factorization) {
 for (int i = 0; i < exp / g; i++)
 mask *= prime;
 }

 return {mask, g};
}

int main() {
 int a1, a2, b1, b2;
 cin >> a1 >> a2 >> b1 >> b2;
 set<int> existing_powers[a2 + 1];
 for (int a = a1; a <= a2; a++) {
 auto [mask, exp] = get_mask(a);
 for (int b = b1; b <= b2; b++)
 existing_powers[mask].insert(exp * b);
 }
 int ans = 0;
 for (auto &powers : existing_powers)
 ans += powers.size();
 cout << ans << "\n";
}

Ideone üzerinden paylaştım.

set yerine tek bir sayı tutup inclusion-exclusion (içerme-dışlama) tekniğini kullandığım bir çözüm daha var. Açıklaması kendisi gibi zor ama oldukça hızlı çalışıyor:

C++:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
 1'den max_power'a kadarki her p için:
 p * 1, p * 2, ..., p * bound
 Kaç farklı sayı olduğunu buluyor.
 (Inclusion-exclusion)
 mn, EKOK'u alınan sayılara dahil olan en küçük sayı.
 mn == 1e9 demek hiç sayı seçmemişiz demek.
*/
ll solve_for_mask(int max_power, int bound, int i = 1, ll lcm = 1, int coef = -1, int mn = 1e9) {
 if (lcm > bound) // 0 gelecektir her türlü.
 return 0;
 if (i == max_power + 1) {
 if (mn == 1e9)
 return 0;
 // Ortak sayılar (mn * bound)'a kadar olacaktır.
 return (ll)coef * mn * bound / lcm;
 }
 ll without = solve_for_mask(max_power, bound, i + 1, lcm, coef, mn);
 lcm = lcm / __gcd(lcm, (ll)i) * i;
 ll with = solve_for_mask(max_power, bound, i + 1, lcm, -coef, mn == 1e9 ? i : mn);
 return without + with;
}
/*
 n = a^k
 En küçük a > 0 için {a, k} döndürüyor.
*/
array<int, 2> get_mask(int n) {
 int init_n = n;
 vector<array<int, 2>> factorization;
 int g = 0;
 for (int i = 2; i * i <= n; i++) {
 if (n % i)
 continue;
 int exp = 0;
 while (n % i == 0)
 n /= i, exp++;
 factorization.push_back({i, exp});
 g = __gcd(g, exp);
 }
 if (n > 1) {
 return {init_n, 1};
 }
 int mask = 1;
 for (auto &[prime, exp] : factorization) {
 for (int i = 0; i < exp / g; i++)
 mask *= prime;
 }
 return {mask, g};
}
int main() {
 int a1, a2, b1, b2;
 cin >> a1 >> a2 >> b1 >> b2;
 vector<int> max_powers(a2 + 1);
 for (int a = a1; a <= a2; a++) {
 auto [mask, exp] = get_mask(a);
 max_powers[mask] = exp;
 }
 ll ans = 0;
 for (int max_power : max_powers) {
 ans += solve_for_mask(max_power, b2) - solve_for_mask(max_power, b1 - 1);
 }
 cout << ans << "\n";
}

Yine Ideone üzerinden paylaştım.

[2, 3000] aralıkları için çalışma süreleri sırasıyla 0.81 ve 0.01 saniye oldu.

Genişletmek için tıkla...

Küçültmek için tıkla...

bicy dedi:

Gereken cevap verilmiş ve "İnternette tonla çözüm var." söylemine ekleyeceğim şey Problem 29'un aslında çözülmesi çok kolay bir problem olması. Ancak anlamadığım tek şey; Eğitim kategorisinde açma amacın? Bir kod istiyorsan internette çokca var, bir kod yazmak istiyorsan doğrudan kod vermek de doğru değil. Kendin yaz, kendi yolundan git. Matematik kafası. Random bir programlama dili kullanacaksın -herhangi bir bilgi vermediğine göre- anladığım kadarıyla. Bundan dolayı problemin nasıl çözüleceğine dair bilgilere internetten ulaşabilirsin. Ben de problemin cevabını vereceğim.

Problemin cevabı 9183'tür.

Ve illa bir kod ile bulacaksan bunları eklemeni öneririm:

1. Nested For-loop
2. Power function
3. Power function üzerinden üreteceğin sayı dizisini tutmak için ayrı bir koleksiyon:

Bir liste, bir NumPY Array olabilir.

Bu yapıları kullanırsan problemin çözümünü neredeyse anında elde edersin. Unutmaman gereken nokta da üretilecek sayıların boyutunu ve hangi veri türlerinin bu kadar büyük sayıları tutabileceğini göz önünde bulundurmak olacak. (tamsayılar işe yaramaz).

Sürprizbozan: ////////////

Write program to calculate pow(x, n) - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

Nested Loops in C with Examples - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

Genişletmek için tıkla...

Küçültmek için tıkla...