GCDEX2 - GCD Extreme (hard)
This problem is a harder version of GCDEX.
Let
For example, , , .
Given , find modulo .
Input
First line of contains (), the number of test cases.
Each of the next lines contains a single integer . ()
Output
For each number , output a single line containing modulo .
Example
Input
5
1
4
100
1000000
100000000000
Output
0
7
13015
4071628673912
5482289417216306300
Explanation for Input
- .
- .
Information
There are 7 Input files.
- Input #0: , , TL = 1s.
- Input #1: , , TL = 20s.
- Input #2: , , TL = 20s.
- Input #3: , , TL = 20s.
- Input #4: , , TL = 20s.
- Input #5: , , TL = 20s.
- Input #6: , , TL = 20s.
My solution runs in 10.7 sec. (total time)
Source Limit is 10 KB.
hide comments
|
Ishan:
2023-03-28 08:35:17
Is enough? Last edit: 2023-03-28 08:35:38 |
|
boomminecraft8:
2019-02-09 01:26:42
As the tag shows, use Dirichlet convolution.
|
|
siyuan:
2018-12-09 12:37:13
This problem is so difficult. If anyone have solved it, please give me some ideas. Thanks a lot! Last edit: 2018-12-09 12:43:48 |
Added by: | Min_25 |
Date: | 2014-06-06 |
Time limit: | 1s-20s |
Source limit: | 10240B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | GCDEX |