QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#726857 | #5626. Sum Kind of Problem | sefnuray# | 100 ✓ | 3ms | 3696kb | C++14 | 1.5kb | 2024-11-09 09:36:42 | 2024-11-09 09:36:43 |
Judging History
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";
}
}
详细
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