NIRVANA

Problem

jzptab

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;512\;MB}$

Description

求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)$，答案模$10^9+9$输出。
多组询问。

Input

一个正整数$T$表示数据组数。
接下来$T$行，每行两个正整数 表示$N,M$。

Output

$T$行，每行一个整数，表示第$i$组数据的结果。

Problem

【HNOI2008】玩具装箱toy

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

$P$教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。$P$教授有编号为$1\sim N$的$N$件玩具，第$i$件玩具经过压缩后变成一维长度为$C_i$.为了方便整理，$P$教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第$i$件玩具到第$j$个玩具放到一个容器中，那么容器的长度将为 $x=j-i+\sum_{k=i}^{j}C_k$制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为$X$,其制作费用为$(X-L)^2$.其中$L$是一个常量。$P$教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过$L$。但他希望费用最小.

Input

第一行输入两个整数$N,L$.接下来$N$行输入$C_i$.
$1\le N\le50000,1\le L,C_i\le10^7$

Output

输出最小费用.

Problem

【ZJOI2007】仓库建设

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

$L$公司有$N$个工厂，由高到底分布在一座山上。如图所示，工厂$1$在山顶，工厂$N$在山脚。由于这座山处于高原内陆地区（干燥少雨），$L$公司一般把产品直接堆放在露天，以节省费用。突然有一天，$L$公司的总裁$L$先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是$L$先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第$i$个工厂目前已有成品$P_i$件，在第$i$个工厂位置建立仓库的费用是$C_i$。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于$L$公司产品的对外销售处设置在山脚的工厂$N$，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送$1$个单位距离的费用是$1$。假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

1. 工厂$i$距离工厂$1$的距离$X_i$（其中$X_1=0$）
2. 工厂$i$目前已有成品数量$P_i$
3. 在工厂$i$建立仓库的费用$C_i$

请你帮助$L$公司寻找一个仓库建设的方案，使得总的费用（$建造费用+运输费用$）最小。

Input

第一行包含一个整数$N$，表示工厂的个数。接下来$N$行每行包含两个整数$X_i, P_i, C_i$, 意义如题中所述。

Output

仅包含一个整数，为可以找到最优方案的费用。

Problem

我是歌手

$\mathrm{Time\;Limit:\;2000\;MS}$
$\mathrm{Memory\;Limit:\;32768\;KB}$

Description

$2013$年一开始，一档音乐节目“我是歌手”就惊艳了大家一回。闲话少说，现在，你成为了这档节目的总导演，你的任务很简单，安排每一期节目的内容。
现在有$N$个歌手，$M$种歌曲流派（$Rock$，$Pop$之类），每个歌手都有自己擅长的流派领域，这些资料都已整理。你的工作是，安排尽可能多场的演唱比赛。每一场比赛所有歌手都必须上场，为了提高收视率，每个人演唱的歌曲类型不能相同，即便一些歌手要被迫选择一些他们不擅长的。同时，为了展现全面性，在不同的演唱比赛上，每个歌手都会安排不同的歌曲流派。
但是问题是，对于任何一个歌曲流派的歌迷，如果超过$K$个不擅长的歌手演唱了这种歌曲，他们就会表示不满，比如，发一些宣泄不满的帖子微博，为了表示观点挑起事端等等。你当然不希望这些事情与你的节目有关，在这个前提下，你可以任意安排尽可能多的比赛场次。

Input

输入第一行为$T$，表示有$T$组测试数据。
每组数据以四个数字$N$，$M$，$L$，$K$开始。$L$表示有$L$组擅长关系，接下来的$L$行，每一行有两个数字$A_i$，$B_i$，表示歌手$A_i$擅长$B_i$类型的歌曲。

Output

对每组数据，先输出为第几组数据，然后输出最多比赛场次。

Problem

DZY Loves Fibonacci Numbers

$\mathrm{Time\;limit:\;4\;Sec}$
$\mathrm{Memory\;limit:\;256\;MB}$

Description

In mathematical terms, the sequence $F_n$ of $Fibonacci$ $numbers$ is defined by the recurrence relation $F_1 = 1,F_2 = 1,F_3=F_1+F_2=3,\cdots F_n = F_{n-1}+F_{n-2}$.
$\mathrm{DZY}$ loves Fibonacci numbers very much. Today $\mathrm{DZY}$ gives you an array consisting of $n$ integers: $a_1, a_2,\cdots,a_n$. Moreover, there are $m$ queries, each query has one of the two types:

1. Format of the query “$1$ $l$ $r$”. In reply to the query, you need to add $F_{i-l+1}$ to each element $a_i$, where $l\le i\le r$.
2. Format of the query “$2$ $l$ $r$”. In reply to the query you should output the value of $\sum_{i=l}^{r}{a_i}$ modulo $10^9+9$.

Help $\mathrm{DZY}$ reply to all the queries.

Input

The first line of the input contains two integers $n$ and $m$ $(1 \le n, m \le 3\times 10^5)$. The second line contains n integers $a_1, a_2, \cdots, a_n (1 ≤ a_i \le10^9)$ — initial array $a$.
Then, $m$ lines follow. A single line describes a single query in the format given in the statement. It is guaranteed that for each query inequality $1 \le l \le r \le n$ holds.

Output

For each query of the second type, print the value of the sum on a single line.

Problem

Calc

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

给出$N$，统计满足下面条件的数对$(a,b)$的个数：

• $1\le a<b\le N$
• $(a+b)|(a\cdot b)$

Input

一行一个数$N$。

Output

一行一个数表示答案。

Problem

【HNOI2011】卡农

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128MB}$

Description

Input

Output

Problem

【JSOI2012】铁拳

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;256\;MB}$

Description

经过了可怕的第三次世界大战后，国家政府崩溃，各大财团趁机夺取掌控世界。长年战争后，八大财团幸存并割据一方，其中最强的当属掌控北美的铁拳。
在铁拳财团所维护的文明区域中，有一项最为光荣、重要的赛事——$\mathrm{Iron\;Fist}$，也就是铁拳大赛。$\mathrm{IF}$中云集了世界各地各财团鼎力资助的世外高手，只为了赢得$\mathrm{IF\;Champion}$，得到无上的荣耀，当然还有随之而来的权力。本来一切秩序井然，但一个来自贫民窟的少年风间仁意外地在海选中赢了$\mathrm{IF}$正式选手，获得了决赛资格，从此格局被打乱……
为了应对这突如其来的变数，$\mathrm{IF}$管理层决定先对联盟中所有的选手进行评估，以更好地掌握大局。
知最近$m$届比赛出现过的$n$位选手，背后都有着各自财团的资助，并且签下了合同。由于这是各财团的高度机密，合同的具体细节无从得知，但铁拳财团的间谍们通过各种渠道得知了每个选手的薪金范围（显然薪金是非负数）。
对于最近$m$届的$\mathrm{IF}$比赛（从$1$开始编号），每一届联盟都会进行清算，通过国际金融手段准确计算出这一届联盟选手身价总和的变化。每一届中，会有一些新选手加入，也会有部分选手在比赛中丧失了战斗能力，而被踢出联盟，流放到贫民窟。
现在给出联盟中$n$位选手的身价范围，以及他们 进入联盟的届数（$0$表示在$m+1$届以前就已经是联盟选手） 和 离开联盟的届数（$0$表示是现役选手）。同时给出最近$m$届中，每一届联盟选手身价总和减去上一届的值。
请你根据现有信息，尽可能准确地给出每个选手可能的薪金范围。各选手之间的薪金范围可以不同时成立，但对于一位选手的范围中的每一个数，都必须至少存在一种合法方案使该选手能得到相应薪金，而且这个范围跨度要尽可能大。
如果输入信息有误，请输出$-1$，表示无解。

Input

第一行一个正整数$m$，意义见上（下同）。
第二行包含$m$个整数，第$i$个表示第$i$届中 选手身价总和 的变化情况。
第三行一个正整数$n$。
接下来n行，每行包含四个整数，分别表示 身价下限 、 身价上限 、 出道届数 、 退役届数，细节请参照上文。
保证出道时间严格比退役时间小（$0$除外）。

Output

一行，输出最小的答案。

Problem

【SCOI2007】最大土地面积

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

在某块平面土地上有$N$个点，你可以选择其中的任意四个点，使得这四个点围成的土地面积最大。

Input

第$1$行一个正整数$N$，接下来$N$行，每行$2$个数$x,y$，表示该点的横坐标和纵坐标。

Output

最大的多边形面积，答案精确到小数点后$3$位。

Problem

矩阵

Time Limit: $10 Sec$
Memory Limit: $128 MB$

Description

Input

第一行两个数$n$、$m$，表示矩阵的大小。
接下来$n$行，每行$m$列，描述矩阵$A$。
最后一行两个数$L$，$R$。

Output

一行，输出最小的答案。