记录编号	147100	评测结果	AAAAAAAAAA
题目名称	[WC 2014]时空穿梭	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	4.651 s
提交时间	2015-01-24 13:39:17	内存使用	121.68 MiB

/*====================Asm.Def========================*/
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <iostream>
using namespace std;
template <typename T>inline void getd(T &x){
	char ch = getchar();bool neg = 0;
	while(!isdigit(ch) && ch != '-')ch = getchar();
	if(ch == '-')ch = getchar(), neg = 1;
	x = ch - '0';
	while(isdigit(ch = getchar()))x = x * 10 + ch - '0';
	if(neg)x = -x;
}
/*======================================================*/
typedef long long LL;
const int maxm = 100000, maxn = 11, maxc = 20;
int C[maxc+2][maxm+2], F[maxc+2][maxm+2], S[maxc+1][maxm+1][maxn+2], mod = 10007;

inline void init(){
	int i, j, c, p;
	for(i = 0;i <= maxm;++i)C[0][i] = 1;
	for(j = 1;j <= maxc;++j)for(i = 1;i <= maxm;++i)
		C[j][i] = (C[j-1][i-1] + C[j][i-1]) % mod;
	
	for(c = 2;c <= maxc;++c)for(i = 1;i <= maxm;++i){
		F[c][i] = (F[c][i] + C[c-2][i-1]) % mod;
		for(j = i<<1;j <= maxm;j += i)
			F[c][j] = (F[c][j] + mod - F[c][i]) % mod;
		p = 1;
		for(j = 0;j <= maxn;++j){
			S[c][i][j] = (S[c][i-1][j] + F[c][i] * p) % mod;
			p = p * i % mod;
		}
	}
}

inline void multi(int *poly, int &n, int a, int b){//poly * (a + bx)
	int i;
	static int tmp[maxn+2];
	for(i = 0;i <= n;++i)tmp[i+1] = poly[i] * b % mod;
	++n;poly[n] = 0;
	for(i = 0;i <= n;++i)poly[i] = (poly[i] * a + tmp[i]) % mod;
}

inline void Query(){
	static int M[maxm+2], seg[maxn*400], tmp[maxn*1000], Poly[maxn], X, n, c;
	int i, j, Ans = 0, Min = maxm + 2, t = 1, cnt = 0;
	getd(n), getd(c);
	for(i = 0;i < n;++i)getd(M[i]), Min = min(Min, M[i]), Poly[i] = 0;
	Poly[n] = 0;
	tmp[0] = 1;
	for(i = 0;i < n;++i){
		int k = max((int)sqrt(M[i]), 1), k2 = M[i] / k;
		for(j = 2;j <= k;++j)if(M[i] / j != M[i] / tmp[t-1])tmp[t++] = j;
		for(j = k2;j >= 1;--j)if(M[i] / tmp[t-1] != j)tmp[t++] = M[i] / (j+1) + 1;
	}
	sort(tmp, tmp + t);
	seg[cnt++] = 1;
	for(i = 0;i < t && tmp[i] <= Min;++i)
		if(seg[cnt-1] != tmp[i])seg[cnt++] = tmp[i];
	seg[cnt] = Min+1;
	for(i = 0;i < cnt;++i){
		if(seg[i+1]-seg[i] < n){//暴力
			for(j = seg[i];j < seg[i+1];++j){
				X = 1;
				for(int k = 0;k < n;++k){
					t = (M[k] / j) % mod;
					X = X * ((M[k] * t + mod - ((t * (t + 1))>>1)* j) % mod) % mod;
				}
				Ans = (Ans + F[c][j] * X) % mod;
			}
		}
		else{
			int p = 1;
			t = (M[0] / seg[i]) % mod;
			Poly[0] = t * M[0] % mod, Poly[1] = mod - ((t * (t+1)) >> 1) % mod;
			for(int k = 1;k < n;++k){
				t = (M[k] / seg[i]) % mod;
				multi(Poly, p, t * M[k] % mod, mod - ((t * (t+1)) >> 1) % mod);
			}
			for(int k = 0;k <= n;++k)
				Ans = (Ans + Poly[k] * (S[c][seg[i+1]-1][k] + mod - S[c][seg[i]-1][k]) % mod) % mod;
		}
	}
	printf("%d\n", Ans);
}

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	//freopen("output.txt", "w", stdout);
	#else
	freopen("WC2014A.in", "r", stdin);
	freopen("WC2014A.out", "w", stdout);
	#endif
	int T;getd(T);
	init();
	while(T--)
		Query();
	
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}