index
:
tcr
master
Team Contest Reference
summary
refs
log
tree
commit
diff
log msg
author
committer
range
path:
root
/
math
/
linearCongruence.cpp
diff options
context:
1
2
3
4
5
6
7
8
9
10
15
20
25
30
35const ll PRIME_SIZE
=
10000000
;
vector
<
int
>
primes
;
//call primeSieve(PRIME_SIZE); before
//Factorize the number n
vector
<
int
>
factorize
(
ll n
) {
vector
<
int
>
factor
;
ll num
=
n
;
int
pos
=
0
;
while
(
num
!=
1
) {
if
(
num
%
primes
[
pos
] ==
0
) {
num
/=
primes
[
pos
];
factor
.
push_back
(
primes
[
pos
]);
}
else
pos
++;
if
(
primes
[
pos
]*
primes
[
pos
] >
num
)
break
;
}
if
(
num
!=
1
)
factor
.
push_back
(
num
);
return
factor
;
}
