問題一覧 > 通常問題

No.1022 Power Equation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 71
作問者 : chocorusk / テスター : 37zigen
お気に入りにしたユーザー ProblemId : 4002 / 自分の提出
問題文最終更新日: 2020-04-08 14:24:44
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 243 (順位表) の他の問題:

Problem Statement

Answer the following $T$ queries.

In the $i$-th query ($1\leq i\leq T$), you are given a positive integer $N_i$. Find the number of tuples $(a, b, c, d)$ of positive integers not exceeding $N_i$ that satisfy $a^b=c^d$.

Input

$T$
$N_1$
$N_2$
$:$
$N_T$

  • $1\leq T \leq 50$
  • $1\leq N_i\leq 10^9$
  • All inputs are integers.

Output

Output $T$ lines. On the $i$-th line ($1\leq i\leq T$), output the answer to the $i$-th query. It can be shown that, under the constraints of this problem, the answer fits in a $64$-bit signed integer type.

Sample

Sample 1
Input
4
1
2
5
314
Output
1
6
49
206958

For example, since $2^4=4^2$, $(a, b, c, d)=(2, 4, 4, 2)$ satisfies the condition in the $3$rd and $4$th queries.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。