ある区間内にある条件を満たすデータの数を出すために、あらかじめ最初からの和を取っておいて後で差を求める、というもの。 n番目までの和をSnと表す時、a番目からb番目までのデータの数はSb - Sa-1と表せる。 (SnはSn-1にn番目のデータの数を加えたものなので、最後は-1)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
void setup(){ | |
size(400, 300); | |
} | |
void draw(){ | |
background(0); | |
fill(255); | |
ellipse(mouseX, mouseY, 10, 10); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
\begin{tikzpicture} | |
\draw[->,>=stealth,thick] (-2,0)--(3,0)node[above]{$x$}; %x軸 | |
\draw[->,>=stealth,thick] (0,-1)--(0,3)node[right]{$y$}; %y軸 | |
\draw (0,0)node[below right]{O}; %原点 | |
\draw[domain=-1.5:1.5] plot(\x,\x+1)node[below right]{$y=x+1$}; | |
\draw (-1,0)node[below]{-1}; | |
\draw (0,1)node[above left]{1}; | |
\end{tikzpicture} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
int gcd(int a, int b) { | |
return b ? gcd(b, a%b) : a; | |
} | |
int lcm(int a, int b) { | |
return a / gcd(a, b) * b; | |
} | |
int digsum(int n) { | |
int res = 0; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// extgcd(a, b, &x, &y): a, b(a = qb + r ---(1))が与えられるとき、ax + by = 1 ---(2)となる(x, y)を求める | |
// (2)に(1)を代入したとき、(qb + r)x + by = 1 ⇔ b(qx + y) + rx = 1 | |
// ここで、extgcd(b, a % b, &s, &t)、すなわち、bs + rt = 1が成り立つとき | |
// s = qx + y, t = x ⇔ x = t, y = s - qx = s - a/b * x | |
long long extgcd(long long a, long long b, long long &x, long long &y) { | |
if (b == 0) { | |
x = 1; | |
y = 0; | |
return a; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
using namespace std; | |
int main() | |
{ | |
int n; cin >> n; cout << n << ":"; | |
int i = 2; | |
while(n != 1) | |
{ | |
if(n % i == 0) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
struct UnionFind | |
{ | |
vector<int> parent; | |
UnionFind(int n) : parent(n) { | |
for(int i = 0; i < n; i++) parent[i] = i; | |
} | |
int root(int x){ | |
return x == parent[x] ? x : (parent[x] = root(parent[x])); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <algorithm> | |
#include <vector> | |
using namespace std; | |
int main() | |
{ | |
vector<int> a, b, c; | |
int n, inp; | |
long long int ans = 0; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <queue> | |
#include <algorithm> | |
using namespace std; | |
#define rep(i, n) for(int (i) = 0; (i) < (n); (i)++) | |
int main(){ | |
int r, c; cin >> r >> c; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <algorithm> | |
using namespace std; | |
#define REP(i, N) for(int (i) = 0; (i) < (N); (i)++) | |
#define N 1000001 | |
#define MAX 1 << 20 | |
int main(){ | |
int n, ai, bi, s[N+1]; |
NewerOlder