#P2619. [Usaco 2012 Mar]Large Banner

    ID: 1674 传统题 1000ms 512MiB 尝试: 22 已通过: 13 难度: 7 上传者: 标签>CF2200提高边界格点 GCD 计数莫比乌斯反演线性筛交换求和顺序倍数枚举等差数列求和贡献法

[Usaco 2012 Mar]Large Banner

背景

农夫约翰要为牛奶制品从长途旅行中返回根西岛的欢迎横幅悬挂一个漂亮的“欢迎回家”的横幅。

题目描述

约翰的田地尺寸为 M×NM \times N (1≤M,N≤100,0001 \leq M, N \leq 100,000),在田地的每一个可能的点都安装了一个支柱,坐标都是整数。

在这 (M+1)×(N+1)(M+1) \times (N+1) 个点中,约翰必须选择两个作为横幅的端点。约翰要求横幅必须完全笔直,即选择的两个支柱之间的直线段上不能有其他支柱。此外,约翰希望横幅的长度至少为 LL,最多为 HH (1≤L≤H≤150,0001 \leq L \leq H \leq 150,000)。

约翰需要你帮助计算他可以悬挂横幅的可能方法有多少种,由于这个数字可能非常大,约翰只想知道模 BB(1≤B≤1,000,000,0001 \leq B \leq 1,000,000,000)的值是多少。

简单题面

给定 n,m,l,hn,m,l,h,问有多少点 A(ax,ay),B(bx,by)A(ax,ay),B(bx,by) 满足:ax,bx∈[0,n]ax, bx \in [0, n],ay,by∈[0,m]ay, by \in [0, m],l≤AB≤hl \leq AB \leq h,且线段 ABAB 上除 A,BA,B 外无整点。

输入格式

第一行包含五个用空格分隔的整数:M,N,L,HM, N, L, H 和 BB。

输出格式

第一行:一个整数,表示可能的横幅数量(模 BB)。

示例

输入1

2 2 1 3 100

输出1

28