F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

a*b problem

Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 71    Accepted Submission(s): 36


Problem Description
标题是骗你进来的,题目内容对标题有稍加扩展

$ a=1 $,$ b=x_1^{t_1}x_2^{t_2}...x_k^{t_k} $,$ 1\leq ab\leq n $

其中$ gcd(x_1,x_2,...,x_k)=1 $ ,$ x_i $为正整数

求满足以上条件的有序数对 $ (x_1,x_2,...,x_k) $ 数量,答案对 $ 10^9+7 $ 取模
 

Input
第一行有一个整数 $ T $ ,代表数组组数

每组数据包含两行:

第一行输入两个数 $ n $,$ K $

第二行输入 $K$ 个数,$t_1, t_2, ..., t_K$

$1\leq T\leq 3$

$ 1\leq n\leq 10^{10} $

$ 1\leq k\leq 10^5 $

$ 1\leq t_i\leq 33 $
 

Output
有序数对 $ (x_1,x_2,...,x_k) $ 数量,答案对 $ 10^9+7 $ 取模
 

Sample Input
3 10 2 1 1 1000 4 1 2 3 4 10000000000 6 2 3 2 1 1 4
 

Sample Output
23 2005 346920481
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-11-23 04:53:50, Gzip enabled