HDU3292 No more tricks, Mr Nanguo因陋就简 特殊不定方程 + 矩阵应用

HDU3292 No more tricks, Mr Nanguo滥竽充数 特殊不定方程 + 矩阵应用

好题目！过的人比较少，不过咱还是过了，所以没关系，题目的综合力很好，题目讲的是南郭先生的故事，

题意：

国王喜欢听演奏，他喜欢的一个正方形 每行X个人来演奏，后来他挂了，他儿子喜欢 把原来的正方形拆成若干个小正方形，南郭很害怕，所以跑路了，他跑了以后，新的国王发现剩下的人刚好可以分成每组Y^2个人的 N组

总是做算法，不如来个陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/

所以我们可以得到一个方程X^2 - 1  == N * Y^2,那么其实就是求解方程X^2 - N * Y^2 ==1,

如果n是完全平方数的话 肯定是无解的，

有解的话就用矩阵来暴力求解

矩阵给出

求出方程第K大的解就可以了

#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>

#define ll long long

#define eps 1e-8

#define inf 0xfffffff

//const ll INF = 1ll<<61;

using namespace std;

//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;

const int MOD = 8191;
const int M = 2;

typedef struct Matrix {
	int m[4][4];
};

Matrix per,d;

int x,y,n,k;

void init() {
	y = 1;
	while(true) {
		x = (ll)sqrt(n * y * y * 1.00 + 1.00);
		if(x * x - n * y * y == 1)break;
		y++;
	}
}

void clear() {
	for(int i=0;i<M;i++) 
		for(int j=0;j<M;j++)
			per.m[i][j] = (i == j);//单位矩阵
	d.m[0][0] = x%MOD;
	d.m[0][1] = n*y%MOD;
	d.m[1][0] = y%MOD;
	d.m[1][1] = x%MOD;
}

Matrix multi(Matrix a,Matrix b) {
	Matrix ans;
	for(int i=0;i<M;i++) {
		for(int j=0;j<M;j++) {
			ans.m[i][j] = 0;
			for(int k=0;k<M;k++)
				ans.m[i][j] += a.m[i][k] * b.m[k][j];
			ans.m[i][j] %= MOD;
		}
	}
	return ans;
}

Matrix quick() {
	Matrix p = d,ans = per;
	while(k) {
		if(k&1) {
			ans = multi(ans,p);
			k--;
		}
		k >>= 1;
		p = multi(p,p);
	}
	return ans;
}

int main() {
	while(scanf("%d %d",&n,&k) == 2) {
		int tmp = (int)sqrt(n*1.00);
		if(tmp * tmp == n) {
			puts("No answers can meet such conditions");
			continue;
		}
		init();
		clear();
		k--;
		d = quick();
		int ans = (d.m[0][0]*x%MOD + d.m[0][1]*y%MOD + MOD)%MOD;
		printf("%d\n",ans);
	}
	return EXIT_SUCCESS;
}