6
5
2015
2

使用fork函数的自动评测系统

最近无聊看了看gty的Gena感觉非常 的高大上。

其实我非常早的就想自己弄一个自动评测软件了,于是学习了以下开始动手。

然后发现有非常多的问题,大部分问题都是用黑科技解决,比如fork之后堆栈不再共用没办法互相传递信息,那么我们就开一个文件来传递信息。

不过还是不少地方借鉴了以下,比如得到内存信息,和时间记录的方式(clock函数会出现一些奇怪的问题)

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <sys/types.h>
#include <unistd.h>
#include <sys/timeb.h>
#include <ctime>
#include <sys/stat.h>
#include <sys/wait.h>
#include <vector>
#include "My_checker.hpp"
using namespace std;

/*
this program is to check a OI program with specific testcases
./checker [-t Time_limit(ms)]{default : 1000} [-T Time_limit(s)] [-m memory_limit(b)]{default:256Mb} [-M memory_limit(mb)] [-f path of programm and testcases]{default: current path} [-F initial file] [-I input files]{default: a.in} [-O output files] {default: a.out} 
*/
void init_file(char *s1);
void show_help();
void work();
vector<string>list;
int init(int argv,char *argc[]){
	for (int i=1;i<argv;i+=2){
		if (!strcmp(argc[i],"--help")){
			show_help();
			return -1;
		}
		if (!strcmp(argc[i],"-t")) sscanf(argc[i+1],"%d",&Time_limit);
		else if (!strcmp(argc[i],"-T")) sscanf(argc[i+1],"%d",&Time_limit),Time_limit*=1000;
		else if (!strcmp(argc[i],"-m")) sscanf(argc[i+1],"%d",&Memory_limit);
		else if (!strcmp(argc[i],"-M")) sscanf(argc[i+1],"%d",&Memory_limit),Memory_limit*=1024*1024;
		else if (!strcmp(argc[i],"-f")){
			sscanf(argc[i+1],"%s",path);
			used_path=1;
		}else if (!strcmp(argc[i],"-F")){
			init_file(argc[i+1]);
			return 1;
		}else if (!strcmp(argc[i],"-I") || !strcmp(argc[i],"-i")){
			Infile=1;
			sscanf(argc[i+1],"%s",input_file);
		}else if (!strcmp(argc[i],"-O") || !strcmp(argc[i],"-o")){
			Outfile=1;
			sscanf(argc[i+1],"%s",output_file);
		}
	} 
	return 0;
}
int type=-1;
int make_file(){
	sprintf(cmd,"ls %s >cur_files_list.ckr",path);
	system(cmd);
	f1=fopen("cur_files_list.ckr","r");
	while (fscanf(f1,"%s",cur)!=EOF){
		list.push_back(string(cur));
	}
	fclose(f1); 
	system("rm -r cur_files_list.ckr");
	sort(list.begin(),list.end());
	 //0 for cpp 1 for c 2 for pas
	char tmp[110];
	for (int i=0;i<list.size();i++){
		int pos=-1;
		if (list[i]==string("cur_files_list.ckr")){
			list.erase(list.begin()+i);
			i--;
			continue;
		}
		if (list[i]==string("My_checker.cpp")){
			list.erase(list.begin()+i);
			i--;
			continue;
		}
		if (list[i]==string("My_checker")){
			list.erase(list.begin()+i);
			i--;
			continue;
		}
		for (int j=0;j<list[i].length();j++){
			if (list[i][j]=='.'){
				pos=j;
				memset(tmp,0,sizeof(tmp));
				for (int k=pos+1;k<list[i].length();k++){
					tmp[k-pos-1]=list[i][k];
				}
				if (!strcmp(tmp,"cpp")){
					if (type!=-1){
						printf("Error : multiple program included\nautochecker failed,please use file style");
						return -1;
					}
					printf("%d\n",pos);
					for (int k=0;k<pos;k++) program_name[k]=list[i][k];
					type=0;
					list.erase(list.begin()+i);
					i--;
				}else if (!strcmp(tmp,"pas")){
					if (type!=-1){
						printf("Error : multiple program included\nautochecker failed,please use file style");
						return -1;
					}
					for (int k=0;k<pos;k++) program_name[k]=list[i][k];
					type=1;
					list.erase(list.begin()+i);
					i--;
				}else if (!strcmp(tmp,"c")){
					if (type!=-1){
						printf("Error : multiple program included\nautochecker failed,please use file style");
						return -1;
					}
					for (int k=0;k<pos;k++) program_name[k]=list[i][k];
					type=2;
					list.erase(list.begin()+i);
					i--;
				}else if (strcmp(tmp,"in") && strcmp(tmp,"out")){
					list.erase(list.begin()+i);
					i--;
				}
				break;
			}
		}
		if (pos==-1){
			list.erase(list.begin()+i);
			i--;
		}
	}
#ifdef DEBUG
	printf("list begin! with %d\n",list.size());
	for (int i=0;i<list.size();i++){
		cout<<list[i]<<endl;
	}
	puts("list end");
#endif
	if (type==-1){
		printf("Error: No program found!\n checker failed");
		return -1;
	}
}
int Result,Running;
inline int testcase(string input,string output,string program_name){
#ifdef DEBUG
	printf("check(%s,%s)\n",input.c_str(),output.c_str());
#endif
	if (used_path) sprintf(cmd,"cat %s/%s > %s",path,input.c_str(),input_file);
	else sprintf(cmd,"cat %s > %s",input.c_str(),input_file);
#ifdef DEBUGcmd
	puts(cmd);
#endif
	system(cmd);
	timeb times,timet;
	ftime(×);
	int stat;
	int pid=fork();
	if (pid<0){
		printf("checker failed!\n");
		return 5;
	}
	if (pid==0){
		char In[22],Out[22];
	//	if (!Infile) sprintf(In," <%s.in",program_name.c_str());
	//	if (!Outfile) sprintf(Out," >%s.out",program_name.c_str());
		if (used_path) sprintf(cmd,"cd %s && ./%s",path,program_name.c_str());
		else sprintf(cmd,"./%s",program_name.c_str());
	#ifdef DEBUGcmd
		puts(cmd);
	#endif
		int id=system(cmd);
		f2=fopen("finished_running_time.ckr","w");
		fprintf(f2,"finished!");
		fclose(f2);
	#ifdef DEBUG
		printf("son progress return ed normally");
	#endif
		while (1);
		return id;
	}else{
		mem=0; Rtime=0;
		while (1){
			ftime(&timet);
			mem=max(mem,getmemory(pid));
			Rtime=(timet.time - times.time) * 1000 + (timet.millitm - times.millitm);
			if (Rtime>Time_limit){
				Result=2;
				kill_judge(pid);
				Running=0;
			#ifdef DEBUG
				printf("parent progress return ed TLE");
			#endif
				return 0;
			}else if (mem>Memory_limit){
			//	Result=3;
			//	kill_judge(pid);
			//	Running=0;
			#ifdef DEBUG
				printf("parent progress return ed MLE");
			#endif
			//	return 0;
			}
			f1=fopen("finished_running_time.ckr","r");
			if (f1==NULL) continue;
			kill_judge(pid);
			Running=0;
			system("rm -r finished_running_time.ckr");
			break;
		}
	#ifdef DEBUG
		printf("parent progress return ed nomally");
	#endif
		wait(&stat);
		int i=WEXITSTATUS(stat);
	//	printf("son program returned %d\n",i);
		if (i){
			Running=0;
			Result=4;
			return 0;
		}
		Running=0;
		Result=check(output);
		return 0;
	}
}
inline void sleep_with_limit(int T){
	timeb s,t;
	ftime(&s);
	while (1){
		if (Running==0) return;
		ftime(&t);
		if (t.time-s.time>T+1 || t.time-s.time) return;
	}
}
int work_auto()
{
	int tmp=make_file();
	if (tmp==-1){
		return -1;
	}
	int Compile_id;
	if (type==0){
		if (used_path)
			sprintf(cmd,"g++ -o2 %s/%s.cpp -o %s/%s",path,program_name.c_str(),path,program_name.c_str());
		else 
			sprintf(cmd,"g++ -o2 %s.cpp -o %s",program_name.c_str(),program_name.c_str());
		Compile_id=system(cmd);
	}else if (type==1){
		if (used_path)
			sprintf(cmd,"fpc -o2 %s/%s.pas",path,program_name.c_str());
		else sprintf(cmd,"fpc -o2 %s.pas",program_name.c_str());
		Compile_id=system(cmd);
	}else if (type==2){
		if (used_path)
			sprintf(cmd,"gcc -o2 %s/%s.c -o %s/%s",path,program_name.c_str(),path,program_name.c_str());
		else 
			sprintf(cmd,"gcc -o2 %s.c -o %s",program_name.c_str(),program_name.c_str());
		Compile_id=system(cmd);
	}
	if (Compile_id){
		puts(result[5]);
		return 5;
	}
	int Id=0,now;
	if (!Infile){
		if (used_path) sprintf(input_file,"%s/%s.in",path,program_name.c_str());
		else sprintf(input_file,"%s.in",program_name.c_str());
	}
	if (!Outfile){
		if (used_path) sprintf(output_file,"%s/%s.out",path,program_name.c_str());
		sprintf(output_file,"%s.out",program_name.c_str());
	}
	int ip;
	int pre;
	for (ip=0;ip<list.size();ip=pre+2){
		pre=ip;
		Running=1;
		testcase(list[ip],list[ip+1],program_name);
		sleep_with_limit(Time_limit/1000);
		if (!Id) Id=Result;
		printf("%s time:%d memory:%d\n",result[Result],Rtime,mem);
		sprintf(cmd,"rm -r %s",input_file);
		system(cmd);
		if (used_path) sprintf(cmd,"rm -r %s/%s",path,output_file);
		else sprintf(cmd,"rm -r %s",output_file);
		system(cmd);
	}
	return Id;
}
int main(int argv,char *argc[])
{
	int tmp=init(argv,argc);
	if (tmp==-1) return 0;
	else if (tmp==1){
		printf("Error!\n"),show_help();
		return 0;
	}else if (tmp==2){
		work();
	}else{
		int ret=work_auto();
	}
	return 0;
}
//coder : davidwang
#include <string>
using namespace std;
const int DefaultTime_limit=1000;
const int DefaultMemory_limit=256*2048*2048;
int Time_limit=DefaultTime_limit,Memory_limit=DefaultMemory_limit;
char cmd[1000],cur[110];
char input_file[1000],output_file[1000];
string program_name;
int Infile,Outfile;
FILE *a1,*f1,*f2;
int mem,Rtime;
char path[2500];
int used_path;
char result[100][100]={"Accepted","Wrong Answer","Time Limit Exceeded","Memory Limit Exceeded","Runtime Error","Compile Error"};

// 0: Accepted 1: Wrong Answer 2: TLE 3: MLE 4: RE 5: CE
inline int getmemory(int pid)
{
    sprintf(cmd, "ps -eo pid,rss | grep %d", pid);
    FILE *f = popen(cmd, "r");
    int a;
    fscanf(f, "%d%d", &a, &a);
    pclose(f);
    return a;
}
void kill_judge(int pid)
{
    sprintf(cmd, "kill -s 9 %d", pid);
    system(cmd);
}
void init_file(char *s1){

}
void show_help(){
	printf("this program is to check a OI program with specific testcases\n./checker [-t Time_limit(ms)]{default : 1000} [-T Time_limit(s)] [-m memory_limit(b)]{default:256Mb} [-M memory_limit(mb)] [-f path of programm and testcases]{default: current path} [-F initial file] [-I input files]{default: (s).in} [-O output files] {default: (s).out}\n");
	return;
}
void work()
{
}
char s1[1000010],s2[1000010];
char o1[1000],o2[1000];
inline int check(string output,string checker=string("cmp"))
{
	FILE *fout,*fstd;
//	printf("checker runned!");
	if (used_path) sprintf(o1,"%s/%s",path,output.c_str());
	else sprintf(o1,"%s",output.c_str());
	if (used_path) sprintf(o2,"%s/%s",path,output_file);
	else sprintf(o2,"%s",output_file);
	fstd=fopen(o1,"r");
	fout=fopen(o2,"r");
//	puts(output_file);
//	puts(output.c_str());
	int t=0;
	while (fscanf(fstd,"%s",s1)!=EOF){
		if (fscanf(fout,"%s",s2)==EOF){
			printf("checker log: your output is shorter than standard output\n");
			return 1;
		}
		t++;
	//	puts(s1);
	//	puts(s2);
		if (strcmp(s1,s2)){
			printf("checker log: Wrong with the %d segment!\n",t);
			printf("%s %s\n",s1,s2);
			return 1;
		}
	}
	if (fscanf(fout,"%s",s2)!=EOF){
		printf("checker log: Your output is longer than standard output!\n");
		return 1;
	}
	return 0;
}

放在一个目录下编译就可以用了,暂时只支持linux……

 

 

Category: 未分类 | Tags:
6
4
2015
0

Thusc T3: bzoj 4104[Thu Summer Camp 2015]解密运算

首先对于一个按行向量排序的循环矩阵,任意两列都是一一对应的关系,于是我们只需要找到每行第一列和最后一列的对应关系就行了

结论1 : 第一行就是最后一行排序的结果

结论2 :这个关系是一一对应的,而且对应后的逆结果便是原序列按照字典序第一关键字,位置第二关键字排序之后的位置

这样暴力sort可以解决,然后还可以高大上的用基数排序搞到O(n)

//coder: davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define X first
#define Y second
using namespace std;
#define LL long long
inline int read(){
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar()) ret=ret*10+ch-48;
	return ret*f;
}
const int N = 200010;
pair<int,int>a[N];
int b[N],n,m;
int main()
{
	n=read(); m=read(); n++;
	for (int i=1;i<=n;i++) b[i]=read(),a[i]=make_pair(b[i],i);
	sort(a+1,a+n+1);
	for (int now=a[a[1].Y].Y;b[now];now=a[now].Y){
		printf("%d ",b[now]);
	}
}
//coder: davidwang
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define X first
#define Y second
using namespace std;
#define LL long long
inline int read(){
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar()) ret=ret*10+ch-48;
	return ret*f;
}
const int N = 200010;
int n,m,a[N],cnt[N],next[N],now;
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	n=read();
	m=read();
	for (int i=1;i<=n+1;i++){
		a[i]=read(); cnt[a[i]]++;
		if (a[i]==0) now=i;
	}
	for (int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
	for (int i=m;i;i--) cnt[i]=cnt[i-1]; cnt[0]=0;
	for (int i=1;i<=n+1;i++) next[++cnt[a[i]]]=i;
	int i=1;
	for (now=next[now],i=1;i<=n;i++,now=next[now])
		printf("%d ",a[now]);
	puts("");
	return 0;
}

 

发现刚才头文件比代码要长好多不科学,然后就缩减了一下……当时这么简单的题目都没能做出来.......

Category: 未分类 | Tags: bzoj THOI
6
4
2015
0

- 未命名 -

Category: 未分类 | Tags:
6
4
2015
0

bzoj 2425: [HAOI2010]计数

题意: 给你一个数n(n<10^51),让你把他的各位数字重拍列以下,然后比他小,求方案数

非常简单的数位DP 主要是看一下代码高亮的情况

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <deque>
#include <queue>
using namespace std;
#define LL long long 
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 60;
LL ans,c[N][N],num[N];
char s[N];
inline LL calc(int x){
	LL ret=1;
	for (int i=0;i<=9;i++)
		ret*=c[x][num[i]],x-=num[i];
	return ret;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
#endif
	scanf("%s",s+1);
	int n=strlen(s+1);
	for (int i=1;i<=n;i++) num[s[i]-'0']++;
	c[0][0]=1;
	for (int i=1;i<=n;i++){
		c[i][0]=1;
		for (int j=1;j<=i;j++) c[i][j]=c[i-1][j]+c[i-1][j-1];
	}
	for (int i=1;i<=n;i++){
		for (int j=0;j<s[i]-'0';j++){
			if (!num[j]) continue;
			num[j]--;
			ans+=calc(n-i);
			num[j]++;
		}
		num[s[i]-'0']--;
	}
	printf("%lld\n",ans);
	return 0;
}		
Category: 未分类 | Tags: bzoj 题解 水题集合
6
4
2015
0

Thusc游记

blog搬家之后的第一篇文章竟然是游记

好吧,我这么颓废的人,才不会拿题解坐地一篇文章呢

Day0:

早上坐着火车去了帝都(今年已经来了三次拉)住在高达上的西郊宾馆

帝都的天气可以烤活人,所以下午就我在宾馆里玩百度之星,我开始做的时候已经过去了近两个小时,然后玩了四道题目(其中两个一个是因为我有忘了bc的I64d另外一个神奇的精度问题爆了OJ)然后发现是坑爹的cf赛制然后我前面都是做出两三道题目的……然后前500我是531...

然后就颓在宾馆一直到睡觉

 

Day1:

上午首先坐车到清华大学(着貌似是我第四次来清华?)然后到了拍照集合的地方发现领导都没有来,我们要等1个多小时,然后还实验性的照了几张。

领导来了之后照完相然后去开幕式

开幕式还是那一套但是今年的吴文虎教授讲的给我印象非常深刻(话说thu阳光长跑的记录保持者竟然是现在已经80多岁的吴文虎教授啊啊啊)

然后是唐文斌大神……有一句话放在这里:永远要何必你优秀的人在一起,才可以进步

然后去试机,试机的机器非常有意思,好像是有什么安全系统,每运行一个程序,就要有3s的时间认证以下,然后才跑对拍非常蛋疼(反正thusc的题目那么难,怎么可能用到对拍?!)然后用了30分钟切完了三道题目然后就准备去吃饭这次还是外卖,然后吃完了休息一下准备考试

 

14:00开始考试

首先浏览一遍题目:

T1: 给你一个 $$ n*m $$ 的矩阵 第i行j列位置的数是 $$ A_i xor B_j  $$ 然后p此询问每次询问一个子矩阵的第k大 $$ n<=1000,m<=300000,p<=500 $$

T2 : 给你一个数列有两种操作,第一种是让一个数字平方在对一个给定的数去摸(20个测试点这个数字都不一样但都提前告诉),第二种是求区间和

T3 : 给你一个字符串,他的加密方式是在后面加入一个字符‘\0’然后滚动排序取每列的最后一个加密,给你加密玩的结果让你解密

。。。。。

貌似T2可以向那种区间开跟或者去摸的方式用并查集什么的随便搞搞都会搞到1和0 然后写了一发,为什么这么慢,然后我发现还有循环结,那怎么办,线段数维护每个循环结就好,模数都非常良心,然后循环结最大是60,用并查集维护是不是每个数都在循环结里面然后这样查询的发杂度是 $$ O(m * log(n) )$$ 然后修改如果在循环解里就暴力推动循环解,否则暴力修改这样的发杂度是 $$ O(f(mod) * m * log(n) )$$ 其中 $$ f(mod) $$ 是关于mod的一个函数,大致可以理解为循环结,然后就搞定了……

 

然后这道题目……貌似可以A掉,考虑到上次的难度我觉得当时太厉害了,感觉这样就可以1本稳稳的了

然后就等着那10s对一下的拍发呆

 

然后发现lzr(qmqmqm) 在我身后开始玩水瓶了,难道……?

 

我们还是看看剩下两道题吧

T1: 仔细分析数据范围,这不是可持久化的Trie吗?然后写了一发……回来才发现比标称多了个log然而当时本季测试并没有人和问题

T3: 当时的心情可谓是百感交集(因为马上就要交卷了),然后根本没有心情去管第三道题目(好像管了也写不出来)最暴力,不可能更暴力的十分

然后交卷走人 发现第三题的一个循环的性质可以暴力搞,然后用sort 加速以下可以做到 $$ O(n * log(n)) $$ 然后就滚粗了,发现lzr确实三个小时AK(当时我正好调完T2) 然后开始玩水瓶

 

然后我就感觉滚粗了,今年题目这么简单,我估计不AK进不了面试了,然而我……就当旅游了

后来发现其他一些人有些和我一样有些还差一些,并不是那么的神。。

然后滚回去发现所有省队都在pku和thu的时候,去年已经Au的faebdc在家里欢快的AK了百度之星

然而我也没有心情看第二天的题目,颓了一会儿就滚去睡觉了

 

最后一天上午面试,我5:30就起来了电话8:30才来,去了才发现好像所有人都来了,然后一位老师一句话: 今年面试是差额的!

gg gg gg

 

他是分了几组按姓名拼音字典序排序,所以到我就快中午了

第一个面试官: 六个运动员站成一条直线有多少中方法??

@#¥%……&*不是吧!小学生面试? 一条直线,横着也算竖着也算吧? 于是我就做死的来了一个 $$ 2 * 6! $$

面试官: 哦,你这样想的阿,那之后的问题都不考虑了,就当运动员是一个球体好了

!@#¥!&……*@#

面试管: 一个圆呢……

(我虽然没上过几节数学课也不用这样吧。。。)

面试官: 三男三女隔着站呢?

(感觉智商被鄙视了)

第二个面试官愉快的和我聊了聊写程序

第三个面试官: Q:地球上什么点向南1km向东1km向北1km回到原点

A:北极点!

Q:还有什么点?

(这是什么题目……)

20s之后Q:想不出来?那就下一个问题吧

第四个面试官:Q:你已经进入了清华大学计算机科学技术系,你最感兴趣的专业是什么?(这。。就是做个梦吧)

然后就谈了谈 人生就出来了

出来之后我发现第二个面试官的脑筋急转弯答案是南极点有很多纬线的长度是1的正整分数,然后在那些纬线北部1km的地方都是所求的

然后就结束了

下午是院系介绍和签约,打死都不敢相信签到了一本线,后来才知道今年thu招办被pku的气到了(北大在ZJ和Hn胜选的时候就用1本吧他们省队都签走了)

然后有多睡了一天第二天回来,路上发现我竟然百度之星因为他奇怪的计算方式进了复赛……

总的来说是不错吧

 

Category: 未分类 | Tags: Thusc游记 游记
6
3
2015
0

2693: jzptab

看了这道题目然后发现省队说过,然后手推了一下。 然后发现各种坑点Wa了好几发比如mod10^8+9什么的

$$ ∑_{i=1}^n∑_{j=1}^mlcm(i,j) $$ 枚举因子

$$ =∑_d∑_{i=1}^{[n/d]}∑_{j=1}^{[m/d]}ijd[gcd(i,j)=1] $$ 反演最后一部分

$$ =∑_dd∑_{i=1}^{[n/d]}∑_{j=1}^{[m/d]}ij∑_{e(e|gcd(i,j))}μ(e) $$ 把e放到前面去枚举,注意因为后面i,j变成了i/j,e/j所以要加上e^2

$$ =∑_dd∑_ee^2μ(e)∑_{i=1}^{[n/ed]}∑_{j=1}^{[m/ed]}ij $$ 提到前面来然后枚举 $$ D=d*e $$ 定义 $$ S(n) = ∑_{i=1}^ni $$

$$ =∑_DS(n/d)S(m/d)∑_{d(d|D)}(D/d)^2*μ(D/d)*d $$

后面这一坨是积性的。然后就可以线性筛了,如果利用约束和的条件可以更简单

//coder : davidwang
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <deque>
#include <queue>
using namespace std;
#define LL long long 
#define X first
#define Y second
inline int read()
{
	int ret=0,f=1; char ch;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar())
		if (ch=='-') f=-f;
	for (;'0'<=ch && ch<='9';ch=getchar())
		ret=ret*10+ch-'0';
	return ret*f;
}
const int N = 10000000,mod=(int)1e8+9;
LL h[N+10],prime[N+10],vis[N+10];
int n,m,cnt,T;
int init()
{
	h[1]=1;
	for (int i=2;i<=N;i++){
		if (!vis[i]){
			prime[++cnt]=i;
			h[i]=(i-(LL)i*i)%mod;
		}
		for (int j=1;j<=cnt && i*prime[j]<=N;j++){
			vis[i*prime[j]]=1;
			if (i%prime[j]){
				h[i*prime[j]]=h[i]*h[prime[j]]%mod;
			}else{
				h[i*prime[j]]=h[i]*prime[j]%mod;
				break;
			}
		}
	}
	for (int i=2;i<=N;i++) h[i]=(h[i]+h[i-1])%mod;
	T=read();
	return 0;
}
inline LL S(LL a){
	return (a*(a+1)/2)%mod;
}
inline void solve(int n,int m){
	LL ans=0;
	if (n>m) swap(n,m);
	int last=0;
	for (int i=1;i<=n;i=last+1){
		last=min(n/(n/i),m/(m/i));
		ans=(ans+(S(n/i)*S(m/i)%mod)*(h[last]-h[i-1]+mod)%mod)%mod;
	}
	while (ans<0) ans+=mod;
	printf("%lld\n",ans);
	return;
}
int main(){
	init();
	while (T--){
		int n=read(),m=read();
		solve(n,m);
	}
	return 0;
}
	

 

Category: 未分类 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com