#2566. 「SDOI2018」荣誉称号

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: zjq

题目描述

休闲游戏玩家小Q不仅在算法竞赛方面取得了优异的成绩,还在一款收集钻石的游戏中排名很高。

这款游戏一共有nnn种不同类别的钻石,编号依次为111nnn。小Q已经玩了这款游戏很久了,对于第iii种钻石,他已经收集到了aia_iai个。这款游戏最大的亮点就是,钻石只有一种获得途径,那就是从商城中购买。具体来说,第iii种钻石的单价为bib_ibi点券。为了鼓励玩家充值,每种钻石都没有数量上限,只要肯充钱,就可以拥有任意多的钻石。但是这款游戏并没有开发"丢弃道具"功能,因此小Q不能通过丢弃钻石去完成任务。

最近这款游戏推出了一个限时成就任务,完成任务的玩家可以获得荣誉称号,而完成任务条件则是:给定正整数kkkmmm,对于任意一个整数x(2k≤x≤n)x(2^k\leq x\leq n)x(2kxn)ax+a⌊x2⌋+a⌊x4⌋+a⌊x8⌋+...+a⌊x2k⌋a_x+a_{\lfloor\frac{x}{2}\rfloor}+a_{\lfloor\frac{x}{4}\rfloor}+a_{\lfloor\frac{x}{8}\rfloor}+...+a_{\lfloor\frac{x}{2^k}\rfloor}ax+a2x+a4x+a8x+...+a2kx都要是mmm的倍数。

高玩小Q当然想完成这个限时成就任务,但是在充钱之前他想知道他究竟需要多少点券才能完成这个任务。请写一个程序帮助小Q计算最少需要的点券数量。

输入格式

第一行包含一个正整数TTT,表示测试数据的组数。

每组数据第一行包含9个正整数n,k,m,p,SA,SB,SC,A,Bn,k,m,p,SA,SB,SC,A,Bn,k,m,p,SA,SB,SC,A,B,其中nnn表示钻石种类数,k,mk,mk,m表示任务条件。

为了在某种程度上减少输入量,a[]a[]a[]b[]b[]b[]由以下代码生成:

unsigned int SA, SB, SC;int p, A, B;
unsigned int rng61(){
    SA ^= SA << 16;
    SA ^= SA >> 5;
    SA ^= SA << 1;
    unsigned int t = SA;
    SA = SB;
    SB = SC;
    SC ^= t ^ SA;
    return SC;
}
void gen(){
    scanf("%d%d%d%d%u%u%u%d%d", &n, &k, &m, &p, &SA, &SB, &SC, &A, &B);
    for(int i = 1; i <= p; i++)scanf("%d%d", &a[i], &b[i]);
    for(int i = p + 1; i <= n; i++){
        a[i] = rng61() % A + 1;
        b[i] = rng61() % B + 1;
    }
}

如对数据的生成方式仍有疑问,请参考下发文件中的参考程序。

输出格式

对于每组数据,输出一行一个整数,即最少需要的点券数量。

样例

输入样例 1

2
3 1 2 3 11111 22222 33333 1 1
1 5
2 3
3 6
7 2 3 7 11111 22222 33333 1 1
6 9
4 5
3 7
5 2
2 4
1 7
9 6

输出样例 1

3
14

样例 2

见下发文件。

数据范围与提示

1≤T≤101\le T\le 101T10

1≤k≤101\le k\le 101k102k≤n2^k\le n2kn

1≤p≤min(n,100000)1\le p\le \min(n,100000)1pmin(n,100000)10000≤SA,SB,SC≤100000010000\le SA,SB,SC\le 100000010000SA,SB,SC1000000

1≤A,B,ai,bi≤1071\le A,B,a_i,b_i\le 10^71A,B,ai,bi107

子任务1(30分):满足 1≤n≤10001\le n\le 10001n1000m=2m=2m=2

子任务2(40分):满足 1≤n≤1051\le n\le 10^51n105m≤200m\le 200m200

子任务3(30分):满足 1≤n≤1071\le n\le 10^71n107m≤200m\le 200m200