{"problem":{"name":"[ICPC 2020 Shanghai R] Fibonacci","description":{"content":"In mathematics, the Fibonacci numbers, commonly denoted as $f_n$, is a sequence such that each number is the sum of the two preceding numbers, starting with $1$ and $1$. That is, $f_1 = 1, f_2 = 1$ an","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9825"},"statements":[{"statement_type":"Markdown","content":"In mathematics, the Fibonacci numbers, commonly denoted as $f_n$, is a sequence such that each number is the sum of the two preceding numbers, starting with $1$ and $1$. That is, $f_1 = 1, f_2 = 1$ and $f_n = f_{n-2} + f_{n-1}~(n \\ge 3)$.\n\nThus, the beginning of the sequence is $1, 1, 2, 3, 5, 8, 13, 21,\\ldots$ .\n\nGiven $n$, please calculate $\\sum_{i=1}^{n}{\\sum_{j=i+1}^{n}{g(f_i,f_j)}}$, where $g(x,y) = 1$ when $x \\cdot y$ is even, otherwise $g(x,y) = 0$.\n\n## Input\n\nThe only line contains one integer $n~(1\\le n\\le 10^9)$.\n\n## Output\n\nOutput one number -- $\\sum_{i=1}^{n}{\\sum_{j=i+1}^{n}{g(f_i,f_j)}}$.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9825","tags":["数学","2020","数论","上海","O2优化","ICPC"],"sample_group":[["3","2"],["10","24"],["100","2739"]],"created_at":"2026-03-03 11:09:25"}}