Извиняюсь, невнимательно прочитал условие. Думал, что N может быть большим простым числом. Но в условии задачи даётся понять, что N - составное, да и к тому же N делится на что-то большее 100. Теперь более-менее понятно, как написать ДП.
2 2011-10-21 01:19:47
Тема: 1807. Патроны для Максима (1 ответов, оставленных в Problems)
http://acm.timus.ru/problem.aspx?space=1&num=1807
Итак, как максимизировать НОД - понятно.
Что делать с НОК?
3 2011-10-11 15:30:52
Re: Подборка задач по теории чисел. (2 ответов, оставленных в Algo)
1860 на тимусе!
4 2011-09-25 17:08:11
Тема: Подборка задач по теории чисел. (2 ответов, оставленных в Algo)
Интересуют всякие разные теоретико-числовые задачи. Если кому что-то запомнилось, чего нет в http://acm.timus.ru/problemset.aspx?spa … ag=numbers , прошу поделиться. Необязательно даже с Тимуса.
5 2011-03-10 21:06:23
Re: timus 1752 (7 ответов, оставленных в Problems)
Попробовал реализовать это хитрое решение, оно естественно сработало, за что вам большое спасибо, было интересно.
Хорошая задача, содержит в себе много подзадач (нахождение самых удаленных вершин, вычисление 1-2-4-8-... предков, LCA, etc).
И вот у меня вопрос. Правильно ли я понял идею с вычислением предков? Сделано у меня так:
vector<vector<int> > deg2;
vector<int> st3;
void dfs3(int u)
{
t_verts& verts = G[u];
int h = height[u];
for(int i=1; h-i>=0; i<<=1)
deg2[u].push_back(st3[h-i]);
st3.push_back(u);
for_each(verts.begin(), verts.end(), [] (const int v) { dfs3(v); });
st3.pop_back();
}
// вычисление k-го предка для вершины u
int predcessor(int u, int k)
{
if(k<0 || k>height[u]) for(;;);
if(k==0) return u;
int t=k, x=0;
for(; t!=0; x++,t>>=1); x--;
int p = 1<<x;
return predcessor(deg2[u][x], k-p);
}
int main()
{
// ...
deg2.resize(n);
st3.reserve(maxheight+1);
dfs3(root);
st3.reserve(0);
// ...
}