2014
02-13

# TCE-frep number system

Number theory is one of the oldest branches of pure mathematics, and one of the largest. Of course, it concerns questions about numbers, usually meaning whole numbers or rational numbers (fractions).
Elementary number theory involves divisibility among integers — the division "algorithm", the Euclidean algorithm (and thus the existence of greatest common divisors), elementary properties of primes (the unique factorization theorem, the infinitude of primes), congruences, including Fermat’s little theorem and Euler’s theorem extending it. But the term "elementary" is usually used in this setting only to mean that no advanced tools from other areas are used — not that the results themselves are simple.
Topics in elementary number theory — the solutions of sets of linear congruence equations (the Chinese Remainder Theorem), or solutions of single binary quadratic equations (Pell’s equations and continued fractions), or the generation of Fibonacci numbers or Pythagorean triples — turn out in retrospect to be harbingers of sophisticated tools and themes in other areas. The remaining parts of number theory are more or less closely allied with other branches of mathematics, and typically use tools from those areas.
Also there lots of branches, such as Combinatorial Number Theory, Algebraic Number Theory, Analytic Number Theory, additive number theory, Geometric number theory, Transcendental number theory, etc.
Today give you a function g(n) whose value is the sum of all the divisors of n .
If n satisfies following rule：

We call n is a TCE-frep number，your task is easy，detail to input and output.

Two ways of input:
A x y
(x, y <= 2^63-1)
Q n
(1 <= n <= 2^63-1)

Two ways of input:
A x y
(x, y <= 2^63-1)
Q n
(1 <= n <= 2^63-1)

A 5 70
A 6 6
Q 6
Q 1

2
1
1
0

Magic-Pen3

 Time limit: 1sec. Submitted: 139 Memory limit: 64M Accepted: 100

Source: lilu0355

﻿

lilu为他自己发明的魔法笔而高兴，但是对于艺术他有着很执着的精神，为此他又发明了一种更强大的魔法笔。当在白色线段上画线时，白色线段就会变成红色；当在红色线段上画线时，红色线段就会变成黑色，当在黑色线段上画线时，黑色线段就会变成白色。

### Input

10000)。N表示线段N条单位线段，标号从1开始。接下来有M行输入，表示M条线段。每行包含两个整数X，Y(X ≤
Y)。表示从第X条单位线段到第Y条单位线段之间用魔法笔画线。起始线段为白色。

### Sample Input


10 2
1 5
4 7
5 1
1 2


### Sample Output


3 5 2
3 2 0


普通模擬會超時..

我過的時候是複制了prayan1988的代碼..用到了樹狀數組

有空學習下數狀數組

#include <iostream>

using
namespace std;

const
int 10005;

int
c[N];

int
Lowbit(int m)

{

return m&(-m);

}

void
Change(int k,int m,int num)

{

while(k<=num){

c
[k] += m;

+= Lowbit
(k);

}

}

int
Getsum(int k)

{

int sum 0;

while(k>0){

sum += c
[k];

-= Lowbit
(k);

}

return sum;

}

int
main()

{

int n, m;

int from, to;

while(scanf("%d%d"&n, &m) == 2)

{

memset(c, 0sizeof(c));

for(int 0m; i++)

{

scanf("%d%d"&from, &to);

Change
(from, 1n);

Change
(to 1-1n);

}

int 000;

for(int 1<= n; i++)

{

int Getsum(i) 3;

if(== 0)

w++;

else if(== 1)

r++;

else if(== 2)

b++;

}

printf("%d %d %d\n"w, r, b);

}

return 0;

}

1. 有两个重复的话结果是正确的，但解法不够严谨，后面重复的覆盖掉前面的，由于题目数据限制也比较严，所以能提交通过。已更新算法

2. 题目需要求解的是最小值，而且没有考虑可能存在环，比如
0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
1 0 1 0 1
1 0 0 0 0
会陷入死循环

3. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1))；因为第二种解法如果数组有重复元素 就不正确