問題一覧 > 通常問題

No.3532 Non-Fourth-Power Sets

レベル : / AI推定難易度 : 3125 / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 1
作問者 : GaLLium / テスター : yu23578 Yoyoyo8128 aa36 Germanium32 yt142857
お気に入りにしたユーザー ProblemId : 13130 / 自分の提出
問題文最終更新日: 2026-05-05 08:18:31
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$.
Answer $T$ test cases. In each test case, positive integers $A,B$ are given. Find the number, modulo $10^9+7$, of sets $\mathscr{S}$ of good sets that satisfy the following.
  • 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)$.

Here, $\gcd(x,y),\operatorname{lcm}(x,y)$ denote the greatest common divisor and the least common multiple of $x,y$, respectively. Also, a $4$-th power is an integer that can be written as $N^4$ for some integer $N$.

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もしくは右上の雲マークをクリックしてアカウントを作成してください。