2020年 ICPC 亚洲区域赛（上海）G

斐波那契数列为1，1，2，3，5，8，13，21，…

可以看到，这个数列有以下特点：

奇，奇，偶，奇，奇，偶…

当 x x x 与 y y y 相乘为偶数时， g ( x , y ) = 1 g(x, y) = 1 g(x,y)=1。

计算 ∑ i = 1 n ∑ j = i + 1 n g ( f i , f j ) \sum_{i=1}^n\sum_{j=i+1}^ng(f_i,f_j) ∑i=1n​∑j=i+1n​g(fi​,fj​)

当 x x x 或 y y y 中其中一个为偶数时，他们相乘也为偶数。

当 i i i 为偶数时， j j j 从 i + 1 i+1 i+1 到 n n n 与它相乘，得到的结果也为偶数。而 j j j 从 i + 1 i+1 i+1 到 n n n ，一共有 n − i n - i n−i 个数，因此就有ans += n - i;

当 i i i 为奇数时，若 j j j 从 i + 1 i+1 i+1 到 n n n 中，有 k k k 个偶数，那么答案也会加 k k k 。

那么这个 k k k 怎么求呢？

每三个数中，就有一个数为偶数。在给定的 n n n 个数中，就有 n / 3 n/3 n/3 个数为偶数。

比如， n n n 等于 10 10 10 ，该斐波那契数列为 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 1,1,2,3,5,8,13,21,34,55 1,1,2,3,5,8,13,21,34,55 ，其中的偶数只有 2 , 8 , 34 2,8,34 2,8,34 ，个数刚好为 10 / 3 = 3 10/3 = 3 10/3=3

因此从第 1 1 1 到 i i i 个数中，一共有 i / 3 i/3 i/3 个偶数。从第 1 1 1 到 n n n 个数中，一共有 n / 3 n/3 n/3 个偶数。

那么，从第 i + 1 i+1 i+1 到 n n n 个数中，有 n / 3 − i / 3 n/3-i/3 n/3−i/3个偶数，所以 k = n / 3 − i / 3 k=n/3-i/3 k=n/3−i/3

即，当 i i i 为奇数时，有 ans += n/3 - i/3​ ;

然后，就可以写出这样的代码：