0

How to find the number of arithmetic progressions in {1,2,3,...,n}, including trivial arithmetic progressions of lengths 1,2.

n <= 1e10

a(n+1) = (n + 1)(1 + Sum_{i=1..n} floor(n/i)) - Sum_{i=1..n} itau(i).

I used this formula, and my code is Time Limit Exceeded

enter image description here

//C++
const int mod = 1000000007;

long long L(long long n){
    long long res = n;
    for (int i = 1; i <= n-1; i++)
        res = (res + (n-1)/i * (n+(n-1)%i-i+1) / 2) % mod;
    return res;
}

now I can improve it:

Sum_{k=1..n} floor(n/k) = 2*(Sum_{i=1..floor(sqrt(n))} floor(n/i)) - floor(sqrt(n))^2

Sum_{i=1..n} itau(i) = Sum_{i=1..floor(sqrt(n))} ifloor(n/i)(1+floor(n/i)) - [floor(sqrt(n))(1+floor(sqrt(n)))/2]^2

I need just O(sqrt(n))

Minh Hien
  • 263
  • 1
  • 7
  • 2
    My only advice here is [Don't `#include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h), measure what's your bottleneck, and rearrange that, or find a better algorithm. – πάντα ῥεῖ May 29 '21 at 13:34
  • 1
    whats the aim of this exercise? Why do you use `mod 1000000007` ? I often hear ppl say that `mod some_large_number` would be a trick to calculate big quantities without overflow, but in fact it is just some coding challenge thingy to let participants compute a rather useless result – 463035818_is_not_an_ai May 29 '21 at 13:35
  • Assuming the time limit is 1 sec, looping till 10^10 will give TLE. As a thumb rule, assume looping till 10^6 takes 1 sec. So you need to convert that summation into multiplication which somebody inclined mathematically could answer or find another algorithm. – srt1104 May 29 '21 at 17:26

1 Answers1

2

I have to assume that your intention is to generate L(n) for n from 1 to t.

By saying cin >> n; you are stopping the program to wait for console input, hence the timeout.

Try something like for (int n = 0; n < t; n++) cout >> n >> ' ' >> L(n) >> endl;

(The algorithm works BTW, I generated the 1st 1000 and matched against OEIS List)

AlanK
  • 1,827
  • 13
  • 16