#1713. 「XXOI 2019」等比数列三角形

「XXOI 2019」等比数列三角形

题目描述

求三边都是 n\le n 的整数,且成等比数列的三角形个数

注意三角形面积不能为 00

注意 oeis 中未收录此数列,所以并不需要去搜了

输入格式

一行一个整数 nn

输出格式

一行一个整数表示答案

样例 1

9
10

除去 99 个等边三角形,还有 {4,6,9}\{4, 6, 9\}

100
133

数据范围与提示

一共有 44 个子任务,对于每一个子任务,你只有通过了该子任务的所有测试点,才能获得此子任务的分数

  1. 10pts10pts,保证 n10n \le 10
  2. 20pts20pts,保证 n105n \le 10^5
  3. 20pts20pts,保证 n107n \le 10^7
  4. 50pts50pts,保证 n1012n \le 10^{12}

对于所有数据,有 1n10121 \le n \le 10 ^ {12}