1542C.md (1445B)
1 Source: https://codeforces.com/problemset/problem/1542/C 2 3 C. Strange Function 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Let $f(i)$ denote the minimum positive integer $x$ such that $x$ is not a divisor of $i$. 22 23 Compute $\sum_{i=1}^n f(i)$ modulo $10^9+7$. In other words, compute $f(1)+f(2)+\dots+f(n)$ modulo $10^9+7$. 24 25 Input 26 27 The first line contains a single integer $t$ ($1\leq t\leq 10^4$), the number of test cases. Then $t$ cases follow. 28 29 The only line of each test case contains a single integer $n$ ($1\leq n\leq 10^{16}$). 30 31 Output 32 33 For each test case, output a single integer $ans$, where $ans=\sum_{i=1}^n f(i)$ modulo $10^9+7$. 34 35 Example 36 37 Input 38 39 ``` 40 6 41 1 42 2 43 3 44 4 45 10 46 10000000000000000 47 ``` 48 49 Output 50 51 ``` 52 2 53 5 54 7 55 10 56 26 57 366580019 58 ``` 59 60 Note 61 62 In the fourth test case $n=4$, so $ans=f(1)+f(2)+f(3)+f(4)$. 63 64 * $1$ is a divisor of $1$ but $2$ isn't, so $2$ is the minimum positive integer that isn't a divisor of $1$. Thus, $f(1)=2$. 65 * $1$ and $2$ are divisors of $2$ but $3$ isn't, so $3$ is the minimum positive integer that isn't a divisor of $2$. Thus, $f(2)=3$. 66 * $1$ is a divisor of $3$ but $2$ isn't, so $2$ is the minimum positive integer that isn't a divisor of $3$. Thus, $f(3)=2$. 67 * $1$ and $2$ are divisors of $4$ but $3$ isn't, so $3$ is the minimum positive integer that isn't a divisor of $4$. Thus, $f(4)=3$. 68 69 Therefore, $ans=f(1)+f(2)+f(3)+f(4)=2+3+2+3=10$.