Puoi leggere e provare a risolvere questo problema visitando questo indirizzo: armadio.
Fissiamo . Fissiamo , multiplo di . Calcoliamo . Verifichiamo se , ed eventualmente aggiungiamo al risultato.
La complessità attuale è . Come ottimizzare?
è un divisore di .
Questo segue dal fatto che , sono multipli di , quindi è un multiplo di .
La complessità è .
Riarrangiamo l'equazione iniziale:
(, sono interi positivi tali che )
Le soluzioni di con fissato, , interi positivi, sono se , se .
Per la definizione di , consulta questo indirizzo: Funzione phi di Eulero.
La dimostrazione si basa sul fatto che se e solo se . Gli validi sono quindi tutti gli interi tali che , che sono tranne nel caso in cui .
Poiché è un qualsiasi divisore di , il numero di soluzioni dell'equazione iniziale è .
Prima di eseguire le query, precalcoliamo per ogni : spiegazione dell'algoritmo.
Per ogni query, calcoliamo il risultato iterando sui divisori di .
Con questa soluzione è possibile ottenere punti. Complessità: .
È possibile trovare i divisori di in modo più efficiente.
Precalcoliamo il crivello di Eratostene. Per ogni troviamo i fattori primi in usando il crivello, e poi i divisori in . Complessità: approssimabile a .
Un metodo alternativo è iterare, per ogni , sui suoi multipli, inserendo tra i loro divisori. Complessità: .
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int i, i1, j, k, k1, t, n, m, res, flag[10], a, b, maxn;
vector<int> er, ph, pr;
void find_dv(vector<array<int, 2>> &dv, int p, int cr) {
int i, sz;
sz = dv.size();
if (p == sz) {
res += ph[cr - 1]; return;
}
for (i = 0; i <= dv[p][1]; i++) {
if (i != 0) cr *= dv[p][0];
find_dv(dv, p + 1, cr);
}
}
void eval(int n) {
int k;
vector<array<int, 2>> dv;
while (n != 1) {
k = er[n]; n /= k;
if (!dv.empty() && dv.back()[0] == k) dv.back()[1]++;
else dv.pb({k, 1});
}
find_dv(dv, 0, 1);
}
void evadi(int Q, vector<int>& N) {
maxn = 1 + *std::max_element(N.begin(), N.end());
er.resize(maxn);
ph.resize(maxn);
for (i = 2; i < maxn; i++) {
if (er[i] == 0) {
er[i] = i; pr.pb(i);
}
for (auto u : pr) {
if (u > er[i] || u * i >= maxn) break;
er[u * i] = u;
}
}
ph[1] = 1;
for (i = 2; i < maxn; i++) {
a = er[i]; b = i / er[i];
if (er[b] == a) ph[i] = a * ph[b];
else ph[i] = (a - 1) * ph[b];
}
ph[1] = 0;
for (i = 0; i <= Q - 1; i++) {
res = 0;
eval(N[i]);
N[i] = res;
}
}