|
|
Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | If you have RE5 | KostyaRychkov | 1860. Фибориалы | 1 авг 2020 01:05 | 1 | Try n = 100000 and remember that 1e6 * 1e6 > 2e9. | tl | for_love | 1860. Фибориалы | 3 апр 2014 19:16 | 2 | tl for_love 29 апр 2013 22:12 # include <cstdio> # include <iostream> # include <vector> # include <cstring> # include <algorithm> # include <map> # include <string> # include <set> # include <cmath> using namespace std; const int M = 1e9 + 7; const int N = 1000001; int a[N], n, f[N], prime[170], sz; bool used[N]; void get_primes(){ for (int i = 2; i < 1001; i ++){ for (int j = i + i; j < 1001; j += i) used[j] = true; } for (int i = 2; i < 1001; i ++){ if (!used[i]) prime[sz++] = i; } } int main(){ scanf("%d", &n); get_primes(); f[1] = f[2] = 1; for (int i = 3; i <= n; i ++){ f[i] = f[i - 1] + f[i - 2]; if (f[i] >= M) f[i] -= M; } for (int i = n; i > 1; i --){ int p = i; for (int j = 0; j < sz && prime[j] * prime[j] <= p; j ++){ while (p % prime[j] == 0){ p /= prime[j]; a[prime[j]] += f[n - i + 1]; if (a[prime[j]] >= M) a[prime[j]] -= M; } } if (p > 1){ a[p] += f[n - i + 1]; if (a[p] >= M) a[p] -= M; } } long long ans = 1; for (int i = 1; i <= n; i ++){ ans = (ans * long long((a[i] + 1) % M)) % M; } printf("%lld", ans); return 0; } Otvet MUHAMMAD 3 апр 2014 19:16 | hint (if you need it) | Aneto | 1860. Фибориалы | 12 июл 2012 01:15 | 3 | I had WA5. After I spent some hours i found out that i used 100000007 instead of 1000000007, so, please, be careful. PS. If n=1000000 then answer is 71348251 I hope it will help someone someday. Just write "1000*1000*1000+7" and be happy :) $subject Edited by author 12.07.2012 01:15 | No subject | Mehemmed Veliyev[Azerbaijan] | 1860. Фибориалы | 27 дек 2011 00:22 | 1 | No subject Mehemmed Veliyev[Azerbaijan] 27 дек 2011 00:22 I have a problem : WA2 what is this test ?? help me please Sorry for poor English | No subject | takiemtam | 1860. Фибориалы | 13 окт 2011 04:46 | 11 | I think so. My question is similar How to solve this, i get TLE ? I have the prime factors in 3 maps while(i<=n){ M3=M1; M3+=M2; M3+=factorization(i); M1=M2,M2=M3,M3.clear(); i++; }
I think that precompaled (mod 100000007) fibbonachi numbers 1 1 2 3 5 7 .. may help Yes! All Ok, this methods gaves easy AC 0.171s without precompiled arrays. Precompiled fibonacci array doesn't really help because total algorithm complexity is not linear. But i use *precalculated* Fibonacci array. And also Eratosthenes Sieve. My algo without Sieve. If i=p^k*Q then in F[n] it comes as p^(k*Fib[n-i]) and this moment I need Fib[n-i] precalculed. Edited by author 11.10.2011 21:03 Yeah, it's right. But: > i=p^k*Q - then you need list of all primes <= 10^6, right? This list is very large, so i used sieve. p.s. Does the fibonacci sequence (mod 10^9+7) get periodic? Edited by author 13.10.2011 04:51 F[3] is 6 so it has 4 divisors (1, 2, 3, 6). So answer for N=3 is 4. |
|
|
|