Это игра spoj с gcd id najpwg http://www.spoj.com/problems/NAJPWG/

Question

Я получаю в этом коде любые предложения. Я вычисляю сумму n/i, где n - это input и i идет от 2 до n. , например, в течение 5 пар будет (2,2), (3,3), (4,4), (5,5), (2,4)

#include<stdio.h> 

int main() 
{ 
int i,j,t,n,m; 
long long k; 
scanf("%d",&t); 
for(i=0;i<t;i++) 
{ 
    scanf("%d",&n); 
    m=n/2; 
    k=0; 
    for(j=2;j<=m;j++) 
    { 
     k+=(n/j); 
    } 
    k+=(n-m); 
    printf("Case %d: %lld\n",i+1,k); 
} 
return 0; 
}` 

Answer 1

С вашим кодом очень много проблем.

В широком смысле классификации -

1. оптимизации можно говорить о том, когда вопрос № 2 получает решен.

2. Код дает неправильный ответ. Ваш алгоритм, как правило, неверен. Сбросьте этот подход и подумайте с точки зрения «Эйлера Тота» и элементарного динамического программирования.

Например,

Let's say, the number is N. 

Теперь, N будет содержать все пары, что N-1 имел. В дополнение к этому он также будет содержать несколько более новых (для которых вы можете воспользоваться функцией Euler Totient).

случаи Образец теста для вашей практики -

input- 
25 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
1021 
99998 
99999 
100000 

output- 
Case 1: 0 
Case 2: 0 
Case 3: 1 
Case 4: 2 
Case 5: 4 
Case 6: 5 
Case 7: 9 
Case 8: 10 
Case 9: 14 
Case 10: 17 
Case 11: 23 
Case 12: 24 
Case 13: 32 
Case 14: 33 
Case 15: 41 
Case 16: 48 
Case 17: 56 
Case 18: 57 
Case 19: 69 
Case 20: 70 
Case 21: 82 
Case 22: 204311 
Case 23: 1960304047 
Case 24: 1960339246 
Case 25: 1960399246 

*