注意90项大概就会超出int范围
如果项数太大取模的话,可以参考之前的做法。
如果给你一个数列:a(1) = 1, a(n+1) = 1 + 1/a(n)。
那么它的通项公式为:a(n) = fib(n+1) / fib(n)。
#include<bits/stdc++.h> using namespace std; int f[10005] = {0}; int main(){ int n; cin >> n; f[0] = 1, f[1] = 1; for(int i = 2; i <= n; ++i){ f[i] = f[i-1] + f[i-2]; f[i] = f[i] % 2333333; } cout << f[n] << endl; return 0; }
注意两点:首先,小于2的数都不是素数。其次,只用判断到根号n即可。
#include<bits/stdc++.h> using namespace std; bool sushu(int n){ bool flag = 0; if(n == 1) return 0; //1不是素数 else{ for(int i = 2; i <= sqrt(n); ++i){ if(n % i == 0) return 0; } return 1; } } int main(){ int n; cin >> n; for(int i = n; ;++i){ if(sushu(i) == 1){ cout << i << endl; break; } } return 0; }
用以上方法挨个判断,只能处理10000以内的数。
如下方法是线性复杂度
#include<bits/stdc++.h> using namespace std; //线性素数筛选,prime[0]是素数个数 const int maxn = 1000000 + 5; int prime[maxn]; void getPrime() { memset(prime, 0, sizeof(prime)); for (int i = 2; i <= maxn; i++) { if (!prime[i]) prime[++prime[0]] = i; for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) { prime[prime[j] * i] = 1; if (i % prime[j] == 0) break; } } } int main(){ getPrime(); int a, b; while(cin >> a >> b){ if(a > b) swap(a, b); int ans = 0; for(int i = 1; i <= prime[0]; ++i){ if(prime[i] >= a && prime[i] < b){ ans++; } } cout << ans << endl; } return 0; }
前提:素因数的分解是唯一的!
1000000的素数完全够了,如果有两个素因子都大于1000000,那么这个数会大于1000000000000,超出int范围,所以数顶多只有一个超过1000000,那么只要最后当剩下一个大素因子时,把ans++即可。
#include<bits/stdc++.h> using namespace std; //线性素数筛选,prime[0]是素数个数,prime中其他元素是所有素数 const int maxn = 1000000 + 5; int prime[maxn]; void getPrime() { memset(prime, 0, sizeof(prime)); for (int i = 2; i <= maxn; i++) { if (!prime[i]) prime[++prime[0]] = i; for (int j = 1; j <= prime[0] && prime[j] * i <= maxn; j++) { prime[prime[j] * i] = 1; if (i % prime[j] == 0) break; } } } int main(){ getPrime(); int n; while(cin >> n){ int ans = 0; for(int i = 1; i <= prime[0]; ++i){ while(n % prime[i] == 0){ n = n / prime[i]; ans++; } if(n == 1) break; } if(n > 1) ans++; //对于大于1000000的素因子,不可能两个都大于,这样会超过范围 cout << ans << endl; } return 0; }
有一类题目是这样的
求 (x^y) % p
当y很大的时候,我们不能直接用for去一个一个的乘,因为这样的方法复杂度是O(N)的。
可以把y分解,分解成1+2+4+8…这样翻倍。
#include<bits/stdc++.h> using namespace std; typedef long long int ll; ll mod_pow(ll x, ll y, ll mod){ ll res = 1; while(y > 0){ //只有当该位为1时,去乘此时的x if(y % 2 == 1) res = res * x % mod; x = x * x % mod; y = y / 2; } res = res % mod; return res; } int main(){ ll x, n; cin >> x >> n; cout << mod_pow(x, n, 233333) << endl; return 0; }
如果x大,y也大,两步走,先大数取模,再二分快速幂。
问题: 十本不同的书放在书架上。现重新摆放,使每本书都不在原来放的位置。有几种摆法?
递推公式为:D(n) = (n - 1) * [D(n - 1) + D(n - 2)]
n=1时,0种;n=2时,1种;n=3时,2种。
S = sqrt(p * (p - a) * (p - b) * (p - c))
公式描述:公式中a,b,c分别为三角形三边长,p为半周长,S为三角形的面积。
公式描述:
组合数公式是指从n个不同元素中,任取m(m≤n)个元素并成一组,叫做从n个不同元素中取出m个元素的一个组合。
http://oeis.org/