Проблема: найти
Диапазон n : 1‹= n ‹= 
Основная проблема заключается в обработке запросов (Q), которые могут быть большими. 1 ‹= Q ‹= 
Методы, которые я использовал до сих пор:
Грубая сила
while(Q--)
{
int N;
cin>>N;
for(int i=1;i<=N;i++)
ans += lcm(i,N)/i ;
}
Сложность: 
Предварительная обработка и обработка запросов в
Сначала я создаю таблицу, которая содержит значение функции Эйлера для каждого N. Это можно сделать за O (N).
void sieve()
{
// phi table holds euler totient function value
// lp holds the lowest prime factor for a number
// pr is a vector which contains prime numbers
phi[1]=1;
for(int i=2;i<=MAX;i++)
{
if(lp[i]==0)
{
lp[i]=i;
phi[i]=i-1;
pr.push_back(i);
}
else
{
if(lp[i]==lp[i/lp[i]])
phi[i] = phi[i/lp[i]]*lp[i];
else phi[i] = phi[i/lp[i]]*(lp[i]-1);
}
for(int j=0;j<(int)pr.size()&&pr[j]<=lp[i]&&i*pr[j]<=MAX;j++)
lp[i*pr[j]] = pr[j];
}
Для каждого запроса факторизуем N и добавляем к результату d*phi[d].
for(int i=1;i*i<=n;i++)
{
if(n%i==0)
{
// i is a factor
sum += (n/i)*phi[n/i];
if(i*i!=n)
{
// n/i is a factor too
sum += i*phi[i];
}
}
}
Это занимает O(sqrt(N)) .
Сложность: O(Q*sqrt(N))
Обработка запросов в O(1)
К описанному выше методу решета я добавляю часть, которая вычисляет нужный нам ответ за O(NLogN)
for(int i=1;i<=MAX;++i)
{
//MAX is 10^7
for(int j=i;j<=MAX;j+=i)
{
ans[j] += i*phi[i];
}
}
Это, к сожалению, истекает для заданных ограничений и ограничения по времени (1 секунда).
Я думаю, что это связано с некоторой умной идеей относительно простой факторизации N . Я могу разложить число на простые множители за O(LogN), используя таблицу lp(наименьшее простое число), построенную выше, но я не могу понять, как получить ответ с помощью факторизации.
