# SuperUserDo

## Problem Statement

Fox Ciel just used the command "sudo" (super-user do) to gain administrative privileges in the UNIX-based operating system on her computer. She now wants to install several new programs. Each program has some dependencies: in addition to the program, the package manager has to install some libraries used by the program.
The package repository contains exactly 1000 libraries. For simplicity, we will number them from 1 to 1000, inclusive.
You are given the information about the dependencies of the programs Fox Ciel wants to install. More precisely, you are given the int[]s A and B, both containing the same number of elements. For each valid i, one of the programs needs all libraries that have numbers between A[i] and B[i], inclusive. Note that the programs may have overlapping dependences: multiple programs may require the same library to be installed. Of course, in such cases it is sufficient to install such a library once.
Calculate and return the total number of libraries that need to be installed.

# [codeforces 359C] Prime Number

## Description

Simon has a prime number x and an array of non-negative integers a1, a2, ..., an.

Simon loves fractions very much. Today he wrote out number on a piece of paper. After Simon led all fractions to a common denominator and summed them up, he got a fraction: , where number t equals xa1 + a2 + ... + an. Now Simon wants to reduce the resulting fraction.

Help him, find the greatest common divisor of numbers s and t. As GCD can be rather large, print it as a remainder after dividing it by number 1000000007 (109 + 7).

# [Codeforces 718C] Sasha and Array

## Problem Description

Sasha has an array of integers a1, a2, ..., an. You have to perform m queries. There might be queries of two types:

1. 1 l r x — increase all integers on the segment from l to r by values x;
2. 2 l r — find , where f(x) is the x-th Fibonacci number. As this number may be large, you only have to find it modulo 109 + 7.

In this problem we define Fibonacci numbers as follows: f(1) = 1, f(2) = 1, f(x) = f(x - 1) + f(x - 2) for all x > 2.

Sasha is a very talented boy and he managed to perform all queries in five seconds. Will you be able to write the program that performs as well as Sasha?

# Codeforces Round#369 Div.2

## A. Bus to Udayland

ZS the Coder and Chris the Baboon are travelling to Udayland! To get there, they have to get on the special IOI bus. The IOI bus has nrows of seats. There are 4 seats in each row, and the seats are separated into pairs by a walkway. When ZS and Chris came, some places in the bus was already occupied.

ZS and Chris are good friends. They insist to get a pair of neighbouring empty seats. Two seats are considered neighbouring if they are in the same row and in the same pair. Given the configuration of the bus, can you help ZS and Chris determine where they should sit?

# [bzoj 1025][SCOI2009] 游戏

## Description

windy学会了一种游戏。对于1到N这N个数字，都有唯一且不同的1到N的数字与之对应。最开始windy把数字按顺序1，2，3，……，N写一排在纸上。然后再在这一排下面写上它们对应的数字。然后又在新的一排下面写上它们对应的数字。如此反复，直到序列再次变为1，2，3，……，N。

1 2 3 4 5 6
2 3 1 5 4 6
3 1 2 4 5 6
1 2 3 5 4 6
2 3 1 4 5 6
3 1 2 5 4 6
1 2 3 4 5 6

# [bzoj 1053][HAOI2007] 反素数

## Description

对于任何正整数x，其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如果某个正整数x满足：g(x)>g(i) 0<i<x，则称x为反质数。例如，整数1，2，4，6等都是反质数。现在给定一个数N，你能求出不超过N的最大的反质数么？

# [bzoj 1008][HNOI2008] 越狱

## Description

监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱

# [bzoj 1041][HAOI2008] 圆上的整点

## Description

求一个给定的圆(x^2+y^2=r^2)，在圆周上有多少个点的坐标是整数。