信心题

背景

本来这题应该是千山鸟飞绝的，可是这题去年互测时已经出过了，有兴趣可以去围观BZOJ 2827 千山鸟飞绝。

于是换了道信心题给大家涨信心用吧！

描述

从前有一个无穷的表格：

把行标号为 $1, 2, \cdots, +\infty$ ，把列标号为 $1, 2, \cdots, +\infty$ 。
用f(x, y)表示第x行第y个数(不是gcd)
现在给你 $x_1, y_1, x_2, y_2$ ，请求出
$S = \sum_{x = x_1}^{x_2}\sum_{y=y_1}^{y_2}{f(x, y)}$

输入格式

一行，五个正整数 $x_1, y_1, x_2, y_2, mod$ 。且满足 $x_1 \leq x_2$ ， $y_1 \leq y_2$ 。

输出格式

一行，一个整数表示 $S$ 对 $mod$ 取模的值。

样例输入

2 1 5 3 10007

样例输出

样例解释

2 + 3 + 4 + 3 + 4 + 5 + 4 + 5 + 6 + 5 + 6 + 7 = 54

数据范围与约定

对于10%的数据， $x_1, y_1, x_2, y_2 \leq 1000$ 。
对于100%的数据， $x_1, y_1, x_2, y_2 \leq 10^{18}, mod \leq 10^9$ 。

来源

VFleaKing

提交代码

背景