This question is from an online coding platform.
Given two integers N and X, find whether sum of squares of fibonacci numbers from 1 to N (both inclusive) is co-prime with Xth fibonacci number or not.
Print "Yes" if it is divisible or "No" otherwise (without quotes).
Input:
- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains two space-separated integers N and X.
Output: For each test case, print the answer.
Constraints:
- $1 ≤ T ≤ 10^5$
- $1 ≤ N, X ≤ 10^9$
Example:
Input:
2
4 2
23673332 12
Output:
Yes
No
Explanation:
Test Case 1 : F12 + F22 + F32 + F42 = 12 + 12 +
22 + 32 = 1 + 1 + 4 + 9 = 15 and 15 is co-prime
with F2 which is 1.
I came up with a solution which uses these facts:
- $\sum_{i=0}^n F_i^2 = F_n.F_{n+1}$
- $GCD(F_n, F_{n+1}) = 1$
- $GCD(F_m, F_n) = F_{GCD(m, n)}$
Here my Java Solution but it is not getting accepted.
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
int x = sc.nextInt();
if (gcd(n, x) == 1 && gcd(n + 1, x) == 1) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
sc.close();
}
static long gcd(long a, long b) {
if (b > a) {
return gcd(b, a);
}
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
}
If I change condition gcd(n, x) == 1 && gcd(n + 1, x) == 1
to gcd(n, x) <= 2 && gcd(n + 1, x) <= 2
then it gets accepted.
Can anyone shed some lights on why is this happening?
Best Answer
Now that I analyzed my solution again I foud out that I was making a silly mistak.
Let me show what
The problem lies in the fact that $GCD(F_m, F_n) = F_{GCD(n, m)}$ hence whenever
gcd(n, x) <= 2 && gcd(n + 1, x) <= 2
is true we know for sure that $F_1 = 1$ or $F_2 = 1$ is the answer respectively.Hence
$$GCD(F_n, F_m) = 1$$ will always be true(since $F_1 = 1$ and $F_2 = 1$).