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

GCD?LCM!

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 499    Accepted Submission(s): 332


Problem Description
First we define:
(1) $lcm(a,b)$, the least common multiple of two integers $a$ and $b$, is the smallest positive integer that is divisible by both $a$ and $b$. for example, $lcm(2,3)=6$ and $lcm(4,6)=12$.
(2) $gcd(a,b)$, the greatest common divisor of two integers $a$ and $b$, is the largest positive integer that divides both $a$ and $b$ without a remainder, $gcd(2,3)=1$ and $gcd(4,6)=2$.
(3) $[exp]$, $exp$ is a logical expression, if the result of $exp$ is $true$, then $[exp]=1$, else $[exp]=0$. for example, $[1+2\geq 3]=1$ and $[1+2\geq 4]=0$.

Now Stilwell wants to calculate such a problem:
$$F(n)=\sum_{i=1}^n\sum_{j=1}^n~[~lcm(i,j)+gcd(i,j)\geq n~] \\
S(n)=\sum_{i=1}^nF(i)$$
Find $S(n)~mod~258280327$.
 

Input
The first line of the input contains a single number $T$, the number of test cases.
Next $T$ lines, each line contains a positive integer $n$.
$T\leq 10^5$, $n\leq 10^6$.
 

Output
$T$ lines, find $S(n)~mod~258280327$.
 

Sample Input
8 1 2 3 4 10 100 233 11037
 

Sample Output
1 5 13 26 289 296582 3928449 213582482
 

Author
SXYZ
 

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-21 21:15:32, Gzip enabled