QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726857#5626. Sum Kind of Problemsefnuray#100 ✓3ms3696kbC++141.5kb2024-11-09 09:36:422024-11-09 09:36:43

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 09:36:43]
  • 评测
  • 测评结果:100
  • 用时:3ms
  • 内存:3696kb
  • [2024-11-09 09:36:42]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <bitset>
#include <vector>
#include <cmath>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <sstream>
#include <iomanip>
#include <stdexcept>
#include <utility>
#include <deque>
using namespace std;
typedef long long ll;
typedef long double ld;
#define MOD 1000007

ll gcd (int a, int b) {
    return b ? gcd (b, a % b) : a;
}

void FastDoubling (ll n, ll res[]) {
    ll a, b, c, d;
    // Base Condition
    if (n == 0) {
        res[0] = 0;
        res[1] = 1;
        return;
    }
    FastDoubling((n / 2), res);
 
    // Here a = F(n)
    a = res[0];
 
    // Here b = F(n+1)
    b = res[1];
 
    c = 2 * b - a;
 
    if (c < 0)
        c += MOD;
 
    // As F(2n) = F(n)[2F(n+1) – F(n)]
    // Here c  = F(2n)
    c = (a * c) % MOD;
 
    // As F(2n + 1) = F(n)^2 + F(n+1)^2
    // Here d = F(2n + 1)
    d = (a * a + b * b) % MOD;
 
    // Check if N is odd
    // or even
    if (n % 2 == 0) {
        res[0] = c;
        res[1] = d;
    }
    else {
        res[0] = d;
        res[1] = c + d;
    }
}



int main()
{
    // these first two lines speed up input / output significantly
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll p;

    cin>>p;

    while(p--) {
        ll k, n;
        cin>>k;
        cin>>n;

        ll total = (n*(n+1))/2;
        ll oddTotal = n*n;
        ll evenTotal = n*(n+1);

        cout<<k<<" "<<total<<" "<<oddTotal<<" "<<evenTotal<<"\n";

    }
    

}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 100
Accepted
time: 3ms
memory: 3696kb

input:

10000
1 1
2 10
3 1001
4 4
5 5
6 6
7 7
8 8
9 9
10 10
11 11
12 12
13 13
14 14
15 15
16 16
17 17
18 18
19 19
20 20
21 21
22 22
23 23
24 24
25 25
26 26
27 27
28 28
29 29
30 30
31 31
32 32
33 33
34 34
35 35
36 36
37 37
38 38
39 39
40 40
41 41
42 42
43 43
44 44
45 45
46 46
47 47
48 48
49 49
50 50
51 51
52...

output:

1 1 1 2
2 55 100 110
3 501501 1002001 1003002
4 10 16 20
5 15 25 30
6 21 36 42
7 28 49 56
8 36 64 72
9 45 81 90
10 55 100 110
11 66 121 132
12 78 144 156
13 91 169 182
14 105 196 210
15 120 225 240
16 136 256 272
17 153 289 306
18 171 324 342
19 190 361 380
20 210 400 420
21 231 441 462
22 253 484 5...

result:

ok 10000 lines