soj4554 Boring Game HASH

题目

给你一个N*M的矩阵,($a_{ij} \leq NM$)接下来有$1e5$次询问,$x_1,y_1,x_2,y_2$分别为子矩阵左上右下的点,问这个子矩阵中是否$1到size(子矩阵)$这些数都在这个矩阵中出现一次.

题解

我们可以采用hash的方法.

首先hash要满足可计算.

我们如果知道子矩阵的size,那么这个子矩阵中 所有数的和,所有数的平方的和,所有数立方的和等等信息,都可以知道了.那么我们需要先预处理一下原来矩阵中的信息.

记$sum[k][i][j]$为[1,i]*[1,j]矩阵中,每个数的k次方的和.那么有

预处理:

  • $sum[k][i][j]=sum[k][i-1][j]+sum[k][i][j-1]-sum[k][i-1][j-1]+a[k][i][j]$

询问:

  • $sum[k][x_1..x_2][y_1..y_2]=sum[k][x_2][y_2]+sum[k][x_1-1][y_1-1]-sum[x_1-1][y_1]-sum[x_2][y_1-1]$

这个题开始我hash了5次,但其实只要hash一次,hash一个数的三次方就行了.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
typedef unsigned int uint;
const int maxn = 1010;
uint f[maxn][maxn], g[maxn * maxn];
int main(){
    for(uint i = 1; i <= 1000000; i++)
        g[i] = g[i-1] + i * i * i;
    int n, m;
    while(scanf("%d%d", &n, &m) == 2){
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++){
                scanf("%u", &f[i][j]);
                f[i][j] = f[i][j] * f[i][j] * f[i][j] + f[i-1][j] + f[i][j-1] - f[i-1][j-1];
            }
        int q; scanf("%d", &q);
        for(int k = 0; k < q; k++){
            int x1, y1, x2, y2;
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            uint val = f[x2][y2] - f[x1-1][y2] - f[x2][y1-1] + f[x1-1][y1-1];
            printf("%s\n", val == g[(x2-x1+1)*(y2-y1+1)] ? "YES" : "NO");
        }

    }
    return 0;   
}

CF949A Zebras 瞎搞+set维护

题意

给你一个长度为$200000$的串,让你把这个串分为若干子序列,每个子序列必须为0,1交替出现,比如0,010,01010,等.且原串中每个字符一定属于且属于一个子序列.

比如0010100,我们可以把它分为3个子序列.

长度为3,分别为1,3,4号下标

长度为3,分别为2,5,6号下标

长度为1,分别为7号下标

否则,如果找不到就输出-1.

分析

首先答案一定是$cnt[0]-cnt[1]$个,因为那种子序列0的个数永远比1的个数多1,故多出了多少个0,就是最后答案.

我们从左往右交替找0,1就好啦,如果最后一个元素不为0,那么就无解.

那么我们怎么快速找到还没有利用的0或者1的下标呢?可以考虑用set维护下标,然后每次lower_bound求出下一个下标,这样一直做就可以了.

感觉维护那种只执行1次或者少量几次的下标的话,用set维护真的挺好的

比如以前做的补图最短路,补图强联通块计数,set维护还有哪些点没被访问过

再比如以前做的一个操作让一个数变为它的因子个数的数,用set维护哪些点还可以操作

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<cstring>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN=2e5+7;
set<int>st0,st2;
char s[MAXN];
vector<int>G[MAXN];
int main(){
	scanf("%s",s);
	int len=strlen(s);
	int cnt[2]={0,0};
	for(int i=0;i<len;++i){
		if(s[i]=='0')st0.insert(i),cnt[0]++;
		else st2.insert(i),cnt[1]++;
	}
	if(cnt[0]-cnt[1]<=0){
		printf("-1\n");
		return 0;
	}
	int now=0;
	int q[MAXN],tot=0;
	bool hasAns=true;
	while(cnt[0]){
		int val=-1;
		tot=0;
		while(1){
			auto first=st0.lower_bound(val);
			if(first==st0.end()){
				hasAns=false;
				break;
			}
			val=*first;
	//		printf("val=%d\n",val);
			cnt[0]--;
			q[tot++]=val;

			auto second=st2.lower_bound(val);
			if(second==st2.end()){
				break;
			}
			val=*second;
			cnt[1]--;
			q[tot++]=val;
		}
		if(!hasAns)break;
		for(int i=0;i<tot;++i){
			if(i%2==0)st0.erase(q[i]);
			else st2.erase(q[i]);
			G[now].push_back(q[i]);
		}
		now++;
	}
	if(cnt[1]!=0)hasAns=false;
	if(!hasAns){
		printf("-1\n");
		return 0;
	}
	printf("%d\n",now);
	for(int i=0;i<now;++i){
		int len=G[i].size();
		printf("%d ",len);
		for(int j=0;j<len;++j){
			printf("%d ",G[i][j]+1);
		}
		printf("\n");
	}
	return 0;
}

CF948C Producing Snow 前缀和+二分

题目

Alice likes snow a lot! Unfortunately, this year’s winter is already over, and she can’t expect to have any more of it. Bob has thus bought her a gift — a large snow maker. He plans to make some amount of snow every day. On day i he will make a pile of snow of volume $V_i$ and put it in her garden.

Each day, every pile will shrink a little due to melting. More precisely, when the temperature on a given day is $T_i$, each pile will reduce its volume by $T_i$. If this would reduce the volume of a pile to or below zero, it disappears forever. All snow piles are independent of each other.

Note that the pile made on day i already loses part of its volume on the same day. In an extreme case, this may mean that there are no piles left at the end of a particular day.

You are given the initial pile sizes and the temperature on each day. Determine the total volume of snow melted on each day.

$N \leq 10^9,V_i \leq 10^9 ,T_i \leq10^9$

Output a single line with N integers, where the i-th integer represents the total volume of snow melted on day i.

每天堆一个雪人,如果当天温度为T,那么所有存在的雪人体积减少$min(T,V_{remain})$,问每一天融化的雪的体积数.

1
2
3
4
in:                                       out:
3                               		  5 12 4
10 10 5                         
5 7 2

题解

我们很自然有这样一个思路,考虑每个雪人能完整的撑过哪几天,然后再加上那个不完整的那天.

每天融化的雪量= k*$V_i$+$extra_i$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e5+7;
long long tag[MAXN];
long long  extra[MAXN];
long long  V[MAXN],T[MAXN];
long long sum[MAXN];
int main(){
	int N;cin>>N;
	for(int i=1;i<=N;++i){
		cin>>V[i];
	}
	for(int i=1;i<=N;++i){
		cin>>T[i];
		sum[i]=sum[i-1]+T[i];
	}

	for(int i=1;i<=N;++i){
		int t=V[i];
		int id=upper_bound(sum+1,sum+N+1,t+sum[i-1])-sum;
		tag[i]++;tag[id]--;
		extra[id]+=t-(sum[id-1]-sum[i-1]);
	}

	for(int i=1;i<=N;++i){
		tag[i]+=tag[i-1];
		cout<<tag[i]*T[i]+extra[i]<<" ";
	}
	return 0;
}

LightOJ1060 nth Permutaiton 计数的思想

题目

Given a string of characters, we can permute the individual characters to make new strings. At first we order the string into alphabetical order. Then we start permuting it.

For example the string ‘abba’ gives rise to the following 6 distinct permutations in alphabetical order.

aabb 1

abab 2

abba 3

baab 4

baba 5

bbaa 6

Given a string, you have to find the nth permutation for that string. For the above case ‘aabb’ is the 1st and ‘baab’ is the 4th permutation.

Input starts with an integer T (≤ 200), denoting the number of test cases.

Each case contains a non empty string of lowercase letters with length no more than 20 and an integer n (0 < n < $2^{31}$).

题解

我们有逆康拓展开的思想,就是说,求长度为n的第k的一个排列(n从0开始).

比如说求长度为4的第5大的排列.

  • 先考虑第一个数,如果为1,那么能确定这个排列一定比 $0X3!=0$个数大,如果为2的话,那么可以确定,这个排列一定比$1X3!=6$个数大所以第一位应该填1,然后求剩余3位数中第5大的排列.
  • 考虑第二个数,按照上面分析,那么这该位应该为4,然后求剩余2位数中排第1大的数
  • 那么最后的排列应该为:1432

那么这个题可以利用同样的思想,只不过要考虑要去重的问题,方法就是

​ 如果当前为x,那么我们就计算有多少个排列一定比它小,这样一直做下去就得到了答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<cstdio>
#include<cstring>
char s[25];
int cnt[500],sum[500];
long long  fac[25];
void init(){
	fac[0]=1;
	for(int i=1;i<=20;++i)fac[i]=fac[i-1]*i;
}
long long n;
long long calc(int ch){
	long long res=0;
	int sum=0;
	int x[500];
	for(int i='a';i<='z';++i){
		sum+=cnt[i];
		x[i]=cnt[i];
	}
	for(int i='a';i<ch;++i){
		if(!x[i])continue;//如果当前位选择i,会导致多少比他小(全排列的值)
		long long tmp=fac[sum-1];
		x[i]--;
		for(int i='a';i<='z';++i){
			tmp/=fac[x[i]];
		}
		res+=tmp;
		x[i]++;//还原x[i]
	}
	return res;
}
int len;
void dfs(int id,long long n){
	if(id==len){
		return ;
	}
	int ans='0',bigX=0;
	for(int i='a';i<='z';++i){
		if(!cnt[i])continue;
		long long x=calc(i);
		if(x<=n){
			ans=i;
			bigX=x;
		}
		else{
			break;
		}
	}
	printf("%c",ans);
	n-=bigX;
	cnt[ans]--;
	dfs(id+1,n);
}
int main(){
	int T;scanf("%d",&T);
	init();
	for(int test=1;test<=T;++test){
		scanf("%s%lld",s,&n);
		printf("Case %d: ",test);
		len=strlen(s);
		memset(cnt,0,sizeof(cnt));
		for(int i=0;i<len;++i)cnt[s[i]]++;
		long long maxN=fac[len];
		for(int i='a';i<='z';++i)maxN/=fac[cnt[i]];
		if(n>maxN){
			printf("Impossible\n");
			continue;
		}else{
			n--;//为了从0开始计数
			dfs(0,n);
			printf("\n");

		}
	}
	return 0;
}

LightOJ1057 Collecting Gold 旅行商问题

题目

Finally you found the city of Gold. As you are fond of gold, you start collecting them. But there are so much gold that you are getting tired collecting them.

So, you want to find the minimum effort to collect all the gold.

You can describe the city as a 2D grid, where your initial position is marked by an ‘x’. An empty place will be denoted by a ‘.’. And the cells which contain gold will be denoted by ‘g’. In each move you can go to all 8 adjacent places inside the city.

问从x出发收集完所有黄金并回到x至少需要走多少步,每步可以选择8个方向中的一个.

题解

因为要从x出发,然后回到x,不难想到旅行商问题的方向.

然后就是构图,对我们有意义的是有g有x的点,我们可以把他们两两之间的距离算出来.这样就构成了一个完全图.

从一个点到另一个点的距离为$max(|x_1-x_2|,|y_1-y_2|)$

旅行商问题复杂度$O(n^2*2^n)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define min(a,b) (a<b?a:b)
#define max(a,b) ((a)>(b)?(a):(b))
const int MAXN=25;
const int INF=1e9+7;
char s[MAXN][MAXN];
int cost[MAXN][MAXN];
int x[MAXN],y[MAXN],tot;
int dp[MAXN][1<<16];
void init(){
    for(int i=0;i<tot;++i){
        for(int j=0;j<tot;++j){
            cost[i][j]=max(abs(x[i]-x[j]),abs(y[i]-y[j]));
        }
    }
}
int dfs(int now,int S){//到达now点,有S个黄金的最小步数
    if(dp[now][S]>=0)return dp[now][S];
	if(now==0&&S==0)return 0;
    dp[now][S]=INF;
    for(int i=0;i<tot;++i){
        int num=1<<i;
		//if(i==now)continue; 只有x没有g时,会出问题
        if((num&S)&&S>=num){
            dp[now][S]=min(dp[now][S],dfs(i,S-num)+cost[i][now]);
        }
    }
    return dp[now][S];
}
int main(){
    int T;scanf("%d",&T);
    for(int test=1;test<=T;++test){
        int N,M;scanf("%d%d",&N,&M);
        for(int i=0;i<N;++i)scanf("%s",s[i]);
        tot=0;
        for(int i=0;i<N;++i){
            for(int j=0;j<M;++j){
                if(s[i][j]=='g'||s[i][j]=='x'){
                    x[tot]=i;
                    y[tot++]=j;
                }
            }
        }
        init();
		memset(dp,-1,sizeof(dp));
        printf("Case %d: %d\n",test,dfs(0,(1<<tot)-1));
    }
    return 0;
}

CF846B 思维

题意

有n个任务,每个任务有相同的k个子任务,你可以按任何顺序完成子任务,每完成一个得1分,但如果你把一个任务的所有子任务都完成了,就可以额外的得到一分.每个子任务所需要的时间$ t_i \leq 10^6$, 你有M的时间,求你最多能得多少分.

$n \leq 45,k \leq 45, M \leq 2*10^9 $

分析

问题的难点在于究竟要不要完成一个完整的任务.

比如说这样一组数据.

1
2
2 4 17
1 2 4 7

如果我们选择完成一个完整的任务,可以获得7分,否则可以获得6分.

难点在完成多少个完整的任务上,那么我们是不是就可以枚举这个东西呢,其他的当做不完成 完整的拿来贪心

复杂度 $ O(n^2k)$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=47;
int a[MAXN];
int t[MAXN][MAXN];
int main(){
	int n,k,M;scanf("%d%d%d",&n,&k,&M);
	int sum=0;
	for(int i=0;i<k;++i)scanf("%d",&a[i]),sum+=a[i];
	sort(a,a+k);
	for(int i=0;i<n;++i)
		for(int j=0;j<k;++j)
			t[i][j]=a[j];//n row k col
	int ans=0;
	for(int full=0;full<=n;++full){
		int tmp=M;
		int res=full*(k+1);
		tmp-=sum*full;//the remain time
		if(tmp<0)break;
		for(int j=0;j<k-1;++j){
			for(int i=full;i<n;++i){
				if(tmp>=t[i][j])tmp-=t[i][j],res++;
				else goto flag;
			}
		}
		flag:
		if(res>ans){
			ans=res;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Race to 1 Again 期望

题目

Rimi learned a new thing about integers, which is - any positive integer greater than 1 can be divided by its divisors. So, he is now playing with this property. He selects a number N. And he calls this D.

In each turn he randomly chooses a divisor of D (1 to D). Then he divides D by the number to obtain new D. He repeats this procedure until Dbecomes 1. What is the expected number of moves required for N to become 1.

大概就是说一个数每次除以他的因子,问这个数变为1的步数期望

题解

期望倒着推,概率正着推

很有趣的一道题,和杭电上的飞行棋那题有点像.

很显然:ex[1]=0

然后我们考虑2: 2可以到达1,2,那么ex[2]=$\frac{1}{2} $ex[1]+$\frac{1}{2}$ex[2]+1.

因为2可以到达1或者2概率都为1/2,然后再加上这次所花费的步数1.

同理 ex[6]=$\frac{1}{4}$ex[1]+$\frac{1}{4}$ex[2]+$\frac{1}{4}$ex[3]+$\frac{1}{4}$ex[6]+1.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
//感觉这种记忆化写法挺常见的,以前在区域赛写过一次,
#include<cstdio>
const int MAXN=1e5+7;
double ex[MAXN];
double dfs(int x){
	if(ex[x]>0)return ex[x];
	if(x==1)return ex[1]=0;
	//printf("x=%d\n",x);
	int stack[500],top=0,i;//这个地方开始开的50,爆炸了
	for( i=1;i*i<x;++i){
		if(x%i==0){
			stack[top++]=i;
			stack[top++]=x/i;
		}
	}
	if(i*i==x)stack[top++]=i;
	double res=top;
	for(int j=0;j<top;++j){
		if(stack[j]!=x)res+=dfs(stack[j]);
	}
	return ex[x]=res*1.0/(top-1);
}
int main(){
	int T;scanf("%d",&T);
	for(int test=1;test<=T;++test){
	//	for(int x=1;x<=100000;++x){
			int x;scanf("%d",&x);
		//	printf("x=%d\n",x);
			ex[1]=0.0;
			printf("Case %d: %.7f\n",test,dfs(x));

		//}
	}
	return 0;
}

CF938D 多源最短路

题目

给你$N$个点, 有点权$a[i]$, 有$M$条边, 每条边有边权$c[i]$, 对于每个$i$ ,$j$ 为任意点,求$min(dist(i,j)*2+a[j])$

$N,M \leq 2*10^5$

分析

题目相当于求每个点到图中的最短路,既多源最短路.可以利用堆优化的dijkstra求得.因为堆顶每次都为到改点的距离最小值,我们每次取出堆顶,然后向相邻点扩展即可.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<cstdio>
#include<cstring>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
typedef pair<long long,int> P;
const int MAXN=2e5+7;
const long long INF=1e17;
priority_queue<P,vector<P>,greater<P> >q;
vector<P>G[MAXN];
long long  cost[MAXN],d[MAXN];
int done[MAXN];
int main(){
	int N,M;scanf("%d%d",&N,&M);
	for(int i=0;i<M;++i){
		int a,b;long long c;
		scanf("%d%d%I64d",&a,&b,&c);
		G[a].push_back(P(2*c,b));
		G[b].push_back(P(2*c,a));
	}
	for(int i=1;i<=N;++i){
		scanf("%I64d",&cost[i]);
		q.push(P(cost[i],i));
	}
	for(int i=1;i<=N;++i)d[i]=INF,done[i]=0;

	while(!q.empty()){
		P p=q.top();q.pop();
		int u=p.second;
		if(done[u])continue;
		done[u]=1;
		d[u]=p.first;
		int len=G[u].size();
		for(int i=0;i<len;++i){
			int v=G[u][i].second;
			q.push(P(G[u][i].first+d[u],v));
		}
	}

	for(int i=1;i<=N;++i){
		printf("%I64d ",d[i]);
	}
	return 0;
}

CF891A Pride

题目

A. Pride

You have an array a with length n, you can perform operations. Each operation is like this: choose two adjacent elements from a, say x and y, and replace one of them with gcd(x, y), where gcd denotes the greatest common divisor.

What is the minimum number of operations you need to make all of the elements equal to 1?

Input

The first line of the input contains one integer n (1 ≤ n ≤ 2000) — the number of elements in the array.

The second line contains n space separated integers a1, a2, …, an (1 ≤ ai ≤ 109) — the elements of the array.

Output

Print -1, if it is impossible to turn all numbers to 1. Otherwise, print the minimum number of operations needed to make all numbers equal to 1.

Examples

Copy

1
2
5
2 2 3 4 6

output

1
5

Copy

1
2
4
2 4 6 8

output

1
-1

Copy

1
2
3
2 6 9

output

1
4

题解

  • 如果有x个1,那么显然答案为n-x
  • 如果没有1,考虑最少需要多少操作弄出一个1来,考虑到gcd(x,y)赋值给y更好,因为gcd(x,y)已经少了一些因子,然后问题就转化为求最短的区间使得gcd(L,R)为1.gcd(L,R+1)=gcd(gcd(L,R),a[R+1]))可以O(n^2)求出所有区间的gcd值.
  • 另外这种枚举的方式我觉得挺妙的

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<cstring>
#define min(a,b) (a<b?a:b)
const int MAXN=2007;
const int INF=1e9+7;
int a[MAXN][MAXN];
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
int main(){
	int n;scanf("%d",&n);
	int cnt1=0;
	for(int i=0;i<n;++i){
		scanf("%d",&a[i][i]);
		if(a[i][i]==1)++cnt1;
	}
	if(cnt1!=0){
		printf("%d\n",n-cnt1);
		return 0;
	}
	int ans=1e9+7;
	for(int i=0;i<n;++i){
		for(int j=i+1;j<n;++j){
			a[i][j]=gcd(a[i][j-1],a[j][j]);
			if(a[i][j]==1)ans=min(ans,j-i);
		}
	}
	if(ans==INF)printf("-1");
	else printf("%d\n",n-1+ans);
	return 0;
}

CF938C

题目

Let’s denote a m-free matrix as a binary (that is, consisting of only 1’s and 0’s) matrix such that every square submatrix of size m × m of this matrix contains at least one zero.

Consider the following problem:

You are given two integers n and m. You have to construct an m-free square matrix of size n × n such that the number of 1’s in this matrix is maximum possible. Print the maximum possible number of 1’s in such matrix.

You don’t have to solve this problem. Instead, you have to construct a few tests for it.

You will be given t numbers x1, x2, …, $x_t$. For every img, find two integers n and m (n ≥ m) such that the answer for the aforementioned problem is exactly x .

Input

The first line contains one integer t (1 ≤ t ≤ 100) — the number of tests you have to construct.

Then t lines follow, i-th line containing one integer x (0 ≤ x ≤ $10^9$).

Output

For each test you have to construct, output two positive numbers n and m (1 ≤ m≤ n ≤ 10^9) such that the maximum number of 1’s in a m-free n × n matrix is exactly x. If there are multiple solutions, you may output any of them; and if this is impossible to construct a test, output a single integer  - 1.

Example

input

1
2
3
4
3
21
0
1

output

1
2
3
5 2
1 1
-1

题解

不难发现对于每一个子阵,总是最右下方的那个地方置为0最合适,因为这样的潜力最大.

问题转化为是否存在n,m使得$n^2$-$[n/m]^2$=x.

既是 $a^2-b^2=C $

转化一下 $ (a+b)(a-b)=C$

然后再分解因子搞一搞就可以了.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<cstdio>
const int INF=1e9;
int m,n;
bool judge(int t,int s){
	if(((s+t)&1)||((s-t)&1))return false;
	n=(s+t)/2;
	//printf("n=%d\n",n);
	if(n>INF||n<1)return false;
	int tmp=(s-t)/2;
	for(int i=1;i<=n;++i){
		if(n/i<tmp||n/i<1){
			return false;
		}
		if(n/i==tmp){
			m=i;
			return true;
		}
	}
	return false;
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		int x;scanf("%d",&x);
		if(x==0){
			printf("1 1\n");
			continue;
		}

		bool tag=false;
		for(int i=1;i*i<=x;++i){
			if(x%i==0&&judge(i,x/i)){
				printf("%d %d\n",n,m);
				tag=true;
				break;
			}
		}
		if(!tag)printf("-1\n");
	}
	return 0;
}
|