#include <stdio.h>
 
// 課題3
int rec(int n) {
    if (n == 0) {
        return 3;
    } else if (n == 1) {
        return 0;
    } else if (n == 2) {
        return 2;
    } else {
        return rec(n - 2) + rec(n - 3);
    }
}
 
int main(void) {
    int n = 50;
 
    // n = 0 のときは無視するので、1から開始
    for (int i = 1; i <= n; i++) {
        int a_n = rec(i);
 
        // a_n が n で割り切れる場合
        if (a_n % i == 0) {
            printf("n = %d: rec(n) = %d (割り切れる)\n", i, a_n);
        }
    }
 
    return 0;
}
 
 

I2luY2x1ZGUgPHN0ZGlvLmg+CgovLyDoqrLpoYwzCmludCByZWMoaW50IG4pIHsKICAgIGlmIChuID09IDApIHsKICAgICAgICByZXR1cm4gMzsKICAgIH0gZWxzZSBpZiAobiA9PSAxKSB7CiAgICAgICAgcmV0dXJuIDA7CiAgICB9IGVsc2UgaWYgKG4gPT0gMikgewogICAgICAgIHJldHVybiAyOwogICAgfSBlbHNlIHsKICAgICAgICByZXR1cm4gcmVjKG4gLSAyKSArIHJlYyhuIC0gMyk7CiAgICB9Cn0KCmludCBtYWluKHZvaWQpIHsKICAgIGludCBuID0gNTA7CiAgICAKICAgIC8vIG4gPSAwIOOBruOBqOOBjeOBr+eEoeimluOBmeOCi+OBruOBp+OAgTHjgYvjgonplovlp4sKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47IGkrKykgewogICAgICAgIGludCBhX24gPSByZWMoaSk7CiAgICAgICAgCiAgICAgICAgLy8gYV9uIOOBjCBuIOOBp+WJsuOCiuWIh+OCjOOCi+WgtOWQiAogICAgICAgIGlmIChhX24gJSBpID09IDApIHsKICAgICAgICAgICAgcHJpbnRmKCJuID0gJWQ6IHJlYyhuKSA9ICVkICjlibLjgorliIfjgozjgospXG4iLCBpLCBhX24pOwogICAgICAgIH0KICAgIH0KICAgIAogICAgcmV0dXJuIDA7Cn0KCg==