分类目录归档:数学

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;
}