Я обнаружил эту проблему, когда пытался найти сложную задачу, связанную с суммирующими функциями, но, к моему удивлению, я не ожидал, что мне действительно понадобится применять здесь так много математических и программных концепций. Моей первой задачей было решить эту проблему с помощью предыдущих методов, которые я использовал для решения других задач, но ни один из них не работал. Интуитивное решение этой проблемы простое, а рекурсивная формула удобна для простых случаев. Я нашел сублинейный алгоритм для решения этой проблемы, но не знаю, как вычислить лучшую оценку моей временной сложности.
Заявление
Пусть S(n,m) = ∑ 𝜑(n× i) для 1 ⩽ i ⩽ m. (𝜑 — функция тотента Эйлера)
Вам дано S(510510,10⁶)=45480596821125120.
Найдите S(510510, 10¹¹). Укажите последние 9 цифр вашего ответа.
Решение
Наивное решение
Давайте попробуем самое простое и наивное решение, просто выполнив for:
long long phi(long long n){
long long x = n;
for(int i=2; i*i<=x; i++){
if(x%i == 0){
while(x%i == 0) x /= i;
n -= n/i;
}
}
if(x != 1) n -= n/x;
return n;
}
long long S(int n, long long m){
long long x = 0;
for(long long k=1; k<=1e11; k++){
x += phi(n*k);
}
return x;
}
Давайте проанализируем временную сложность каждой функции, посчитаем 𝜑(n) наивным способом, который в худшем случае может достигать 𝒪(√n). Функция для расчета S(n,m) — это просто for:
Как видите, это ужасная временная сложность для ограничений задачи. Вы можете попытаться вычислить это, но вам понадобится как минимум несколько лет, чтобы закончить это.
Вы можете попытаться улучшить сложность, эффективно вычислив функцию 𝜑(n), но даже если вы сможете сделать это за постоянное время, ваша сложность будет 𝒪(m). Итак, обычное решение этой проблемы заключается в том, чтобы не повторять m, чтобы избежать линейного поведения.
Сублинейный метод
Я уже решал некоторые из этих задач раньше, поэтому моей первой мыслью было применить метод гиперболы с нотацией Дирихле, чтобы посмотреть, смогу ли я свести к чему-то вроде 𝒪(n²ᐟ³), но я не могу найти хороший способ сделать что.
Моя вторая попытка заключалась в использовании функции Мебиуса, у меня больше прогресса в этом, но в какой-то момент я застреваю и не знаю, как действовать, так что опять же, эта идея оказалась бесполезной.
Сложные проблемы требуют простых проблем, в этом есть некоторый смысл. Я имею в виду, давайте попробуем с более простыми случаями.
n простое
Взгляните на функцию S(n, m), когда n — простое число. Для упрощения обозначений я буду использовать букву p:
Это действительно хорошее рекурсивное определение. Разберем его сложность:
В предыдущем посте я объяснил, как вычислить 𝛷(n) в n²ᐟ³. Как видите, это сублинейное решение, которое может завершить задачу за несколько секунд, но к сожалению, n не является простым числом.
n — простая степень
Разберем более общий случай, когда n = pᵏ, для некоторого простого числа p и некоторой степени k>1:
рекурсия аналогична предыдущей, но эта формула может работать для чисел типа 2³⁷, которые больше 10¹¹, но это не то, что требуется для задачи, поэтому нам нужно продолжить поиск общей формулы.
n — произведение двух простых чисел
Теперь давайте разберем случай, когда n = p₁p₂, где p₁ и p₂ — разные простые числа.
Общий случай
Доказательства следующей формулы у меня нет, но поскольку случай двух простых чисел соответствует применению принципа включения-исключения, думаю, имеет смысл думать, что и в общем случае так же бывает:
Проанализируем временную сложность:
Теперь позвольте мне объяснить, что такое f. Чтобы вычислить S(n,m), я перебираю каждое возможное подмножество простых множителей числа n. Хорошая верхняя граница для этой концепции — log(n)/log log(n). Итак, для числа n ожидается, что оно будет иметь log(n)/log log(n) количество различных простых делителей. Итерация по ним занимает 2ˢⁱᶻᵉ, но применение мемоизации к функции S(n,m) означает, что она будет перебирать только различные значения ⌊ m/P⌋, где P — произведение некоторого подмножества простых множителей. Трудно сказать, какова временная сложность, но для упрощения можно считать, что мы перебираем все возможные подмножества в каждом рекурсивном вызове:
мой код находит решение проблемы менее чем за 2 секунды.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using t128 = __int128;
#define N 30000000
#define MOD 1000000000
int phi[N];
int lpf[N];
int Phi[N];
vector <int> f;
vector <int> v;
map <ll, ll> Phi_cache;
map <ll, ll> S_cache;
void cphi(){
phi[1] = 1;
for(int i=2; i<N; i++){
if(!phi[i]){
phi[i] = i-1;
lpf[i] = i;
for(ll j=2*i; j<N; j+=i){
if(phi[j] == 0) phi[j] = j;
phi[j] = phi[j]/i*(i-1);
if(lpf[j] == 0) lpf[j] = i;
}
}
}
for(int i=1; i<N; i++) Phi[i] = (Phi[i-1] + phi[i])%MOD;
}
vector <int> prime_factors(int n){
vector <int> ans;
while(n > 1){
int d = lpf[n];
while(n%d == 0) n /= d;
ans.push_back(d);
}
return ans;
}
ll T(ll n){
t128 ans = n; ans *= (n+1);
ans /= 2;
ans %= MOD;
return ans;
}
ll calc_Phi(ll n){
if(n < N) return Phi[n];
if(Phi_cache.find(n) != Phi_cache.end()) return Phi_cache[n];
ll ans = T(n);
ll sqrt_n = floor(sqrt(n));
for(int m=1; m < n/sqrt_n; m++){
ans -= (1LL*Phi[m]*(n/m - n/(m+1)))%MOD;
ans %= MOD;
}
for(int m=2; m<=sqrt_n; m++){
ans -= calc_Phi(n/m);
ans %= MOD;
}
ans += MOD; ans %= MOD;
Phi_cache[n] = ans;
return ans;
}
ll S(int n, ll m){
if(m == 0) return 0;
if(m == 1) return phi[n];
if(S_cache.find(m) != S_cache.end()) return S_cache[m];
int sz = f.size();
ll ans = (1LL*phi[n]*calc_Phi(m))%MOD;
for(int i=1; i<(1<<sz); i++){
int c = __builtin_popcount(i);
if(c%2 == 0) ans -= S(n, m/v[i]);
else ans += S(n, m/v[i]);
ans %= MOD;
}
if(ans < 0) ans += MOD;
S_cache[m] = ans;
return ans;
}
void fill_mask(){
int sz = f.size();
v.resize((1<<sz));
v[0] = 1;
for(int i=1; i<(1<<sz); i++){
int previous_mask = v[i&(i-1)];
int pos = __builtin_ctz(i&(-i));
int val = previous_mask*f[pos];
v[i] = val;
}
}
int main(){
cphi();
int n; ll m; cin >> n >> m;
f = prime_factors(n);
fill_mask();
cout << S(n, m) << '\n';
return 0;
}
