分类目录归档：数学

洛谷 P3383 【模板】线性筛素数

发表评论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
int n, m;
bool prime[10000005];

int main(){
    memset(prime, true, sizeof(prime));
    cin >> n >> m;
    prime[0] = prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (!prime[i])continue;
        for (int j = 2 * i; j <= n; j += i) {
            prime[j] = false;
        }
    }
    for (int i = 1; i <= m; i++) {
        int tmp;
        cin >> tmp;
        cout << (prime[tmp]?"Yes":"No") << endl;
    }
}

洛谷 P1338 末日的传说

发表评论

可以说是超难的一道题了。。。。
全程题解：
https://www.luogu.org/blog/user11765/solution-p1338

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<algorithm>
using namespace std;
long long n, m, a[50005];
int main() {
    cin >> n >> m;
    long long s = 1, e = n;
    for (long long i = 1; i <= n; i++) {
        long long t = (n - i)*(n - i - 1) / 2;
        if (t >= m)a[s++] = i;
        else {
            a[e--] = i;
            m -= e - s + 1;
        }
    }
    for (int i = 1; i <= n; i++)cout << a[i] << " ";
}

洛谷 P1147 连续自然数和

发表评论

需要用到等差数列的性质，再稍微减减枝就可以了。只要能想到这些，写出来没难度。
令 $a < b$ ，a为首项，b为末项，为等差数列，公差为1。 则有 $(a+b)*(b-a+1)/2=n$。 即 $(a+b)*(b-a+1)=2*n$。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
using namespace std;
int main() {
    long long n;
    cin >> n;
    for (long long a = 1; a <= n/2; a++) {
        for (long long b = a; b <= n/2+1; b++) {
            long long l = (a + b)*(b - a + 1);
            if (l == 2 * n)cout << a << " " << b << endl;
            if (l > 2 * n)break;
        }
    }
}

Codeforces 598A Tricky Sum 技巧求和

发表评论

题目地址：http://codeforces.com/problemset/problem/598/A
这道题目本来一开始是想要搞暴力的，但是第一个就超时。不得已换了个数学方法。
首先用小学生都会的数列求和：（首项+末项）*项数/2 把从1…n的和算出来，然后计算出不大于n的2的幂次共有多少个，用等比数列求和公式求出它们的和，减去两倍即可。
上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<algorithm>
using namespace std;
long long try2(long long n){ //函数try2就是计算从1到n之间所有不大于n的2的幂次之和，可结合等比数列求和公式推导后再领悟，不懂可以看下面或者评论我博客。
    long long m2=1;
    while(m2<=n)m2*=2;
    return m2-1;
}
void process(){
    long long n;
    cin>>n;
    cout<<((1+n)*n/2-2*try2(n))<<endl;
}
int main(){
    int t;
    cin>>t;
    while(t--)process();
}

其实做这道题是要数学功底的。。。我还是把具体的推导过程说一下好了。我们想要求出小于n的所有2的幂次方项之和，根据等比数列求和公式可知:2^0+2^1+2^2+…+2^n=2^{n+1}-1所以我们只要找到最大的小于n的2的幂次再乘2减1就可以了。具体代码可参见函数try2()。

Codeforces 597A Divisibility 整除

发表评论

题目：http://codeforces.com/contest/597/problem/A

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;
inline long long cal(long long a,long long b,long long k){
    return b/k-(a-1)/k;
}
int main(){
    long long k,a,b;
    cin>>k>>a>>b;
    if(a>0)cout<<cal(a,b,k);
    else if(b<0)cout<<cal(-b,-a,k);
    else if(a==0)cout<<b/k+1;
    else if(b==0)cout<<(-a)/k+1;
    else if(a<0&&b>0)cout<<cal(1,b,k)+cal(1,-a,k)+1;
}

洛谷 计算系数

发表评论

题号：P1313
大晚上的刷杨辉三角………………

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
using namespace std;
#define MOD 10007
long long arr[1005][1005];
long long a, b, k, n, m;
long long quickpow(long long x, long long y){
    if (y == 0)return 1;
    long long qpsqr2 = quickpow(x, y / 2)%MOD;
    if (y % 2 == 0){
        return (qpsqr2*qpsqr2) % MOD;
    }
    else{
        return (((qpsqr2*qpsqr2) % MOD)*(x%MOD)) % MOD;
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin >> a >> b >> k >> n >> m;
    for (int i = 0; i <= 1000; i++){
        arr[0][i] = 1;
        arr[i][i] = 1;
    }
    for (int i = 1; i <= 1000; i++){
        for (int j = 1; j < i; j++){
            arr[j][i] = (arr[j][i - 1] % MOD + arr[j - 1][i - 1] % MOD) % MOD;
        }
    }
    long long ans = arr[n][k];
    ans = (ans*quickpow(a, n)) % MOD;
    ans = (ans*quickpow(b, m)) % MOD;
    cout << ans;
    return 0;
}

20180808更新：
不用杨辉三角啦！因为我会乘法逆元啦！！！哈哈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#define PINF 0x7fffffff
#define NINF 0x80000000
using namespace std;
#define MOD 10007
ll a,b,k,n,m;
//C(min(n,m),k)*b^m*a^n
ll quickpow(ll a, ll b) {
    if (b == 0)return 1;
    ll re = quickpow(a, b / 2) % MOD;
    re = (re*re) % MOD;
    if (b % 2 == 1)re *= a % MOD;
    return re % MOD;
}
ll inv(ll x) {
    return quickpow(x, MOD - 2) % MOD;
}
int main() {
    cin >> a >> b >> k >> n >> m;
    ll re = (quickpow(a, n)*quickpow(b, m)) % MOD;
    ll cU = 1;
    for (ll i = k; i >= k - min(n, m) + 1; i--) {
        cU *= i % MOD;
        cU %= MOD;
    }
    ll cD = 1;
    for (ll i = 1; i <= min(n, m); i++) {
        cD *= i % MOD;
        cD %= MOD;
    }
    re = ((re * cU) % MOD*inv(cD)) % MOD;
    cout << re;
}