codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.