問題一覧 > 通常問題

No.1653 Squarefree

レベル : / AI推定難易度 : 1550 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 102
作問者 : chocorusk / テスター : sak
お気に入りにしたユーザー ProblemId : 6592 / 自分の提出
問題文最終更新日: 2021-08-09 09:32:23
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 310 (順位表) の他の問題:

Problem Statement

A positive integer is said to be squarefree if it is not divisible by any perfect square greater than $1$.

Find the number of squarefree integers between $L$ and $R$, inclusive.

Input

$L\ R$

  • $1\leq L\leq R\leq 10^{18}$
  • $R-L\leq 10^6$
  • All inputs are integers.

Output

Output the answer.

Sample

Sample 1
Input
3 14
Output
8

Among the integers between $3$ and $14$, inclusive, the squarefree ones are $3$, $5$, $6$, $7$, $10$, $11$, $13$, $14$, for a total of $8$.

Sample 2
Input
1 1
Output
1

Note that $1$ is squarefree.

Sample 3
Input
998244353 998244853
Output
305

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