|
||||||||||
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
Sample Output
Author SXYZ Source | ||||||||||
|