No.3532 Non-Fourth-Power Sets
レベル :
/ AI推定難易度 : 3125
/ 実行時間制限 : 1ケース 6.000秒 / メモリ制限
: 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 1
作問者 :
GaLLium
/ テスター :
yu23578
Yoyoyo8128
aa36
Germanium32
yt142857
タグ : / 解いたユーザー数 1
作問者 :
Germanium32
yt142857
問題文最終更新日: 2026-05-05 08:18:31
English (AI translation)
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
聖光学院プログラミングコンテスト2026 day2
(順位表)
の他の問題:
Problem Statement
*The time limit for this problem is 6 seconds. Using a fast language is recommended.
A set $S$ of positive integers is called a good set if it satisfies the following.
- For a positive integer $z$, if there exist $x,y \in S$ such that $\dfrac{z}{\gcd(x,y)},\dfrac{\operatorname{lcm}(x,y)}{z}$ are coprime integers, then $z \in S$.
- For $x,y \in S$, $\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}$ is not a $4$-th power greater than $1$.
- The union of all elements of $\mathscr{S}$ is equal to the set of positive divisors of $A^B$.
- For any $X,Y \in \mathscr{S}$, the following holds.
- Let $\omega(x,y)$ be the number of distinct prime factors of $\dfrac{\operatorname{lcm}(x,y)}{\gcd(x,y)}$. For any $x,x^{\prime} \in X$, $\min_{y \in Y} \omega(x,y) = \min_{y \in Y} \omega(x^{\prime},y)$.
Constraints
- All inputs are integers.
- $1 \leq T \leq 10^{6}$
- $1 \leq A \leq 2 \times 10^{7}$
- $1 \leq B \leq 2 \times 10^{6}$
Input
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Here, $\mathrm{case}_t$ is the $t$-th test case, given in the following format.
$A\ B$
Output
Output $T$ lines. On line $t(1 \leq t \leq T)$, output the answer to the $t$-th test case.
Sample
Sample 1
Input
5
12 1
20 2
1 100
9999 9999
16777216 2000000
Output
10
185
1
340129719
720394457
For the first test case, for example, $\mathscr{S} = \lbrace \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace, \lbrace 6 \rbrace, \lbrace 12 \rbrace \rbrace$ satisfies the conditions, and there are $10$ such $\mathscr{S}$ in total. Note that you must output the remainder when divided by $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。