目录

hdu6440  Dream【费马小定理】

hdu6441 Find Integer 【费马大定理】

hdu6446Tree and Permutation【邻接表dfs】


hdu6440  Dream【费马小定理】

传送门

复习费马小定理的定义:

费马小定理:假如p是质数,且gcd(a,p)=1,那么 a^(p-1)≡1(mod p)。即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。

题意:给你一个素数p,让你定义一个互不相关的乘法表和加法表,使(m+n)^p=m^p+n^p(0≤m,n<p)

题解:

因此,(m+n)^p≡m+n (mod p), 同时,m^p+n^p≡m+n (mod p) 因此只要把原来的加法表乘法表mod p 就可以了

AC_code:

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t;
	cin>>t;
	while(t--) {
		int p;
		cin>>p;
		for(int i = 0; i < p; i++) {
			for(int j = 0; j < p; j++) {
				if(j == 0) {
					cout<<(i+j)%p;
				} else {
					cout<<" "<<(i+j)%p;
				}
			}
			cout<<endl;
		}
		for(int i = 0; i < p; i++) {
			for(int j = 0; j < p; j++) {
				if(j == 0) {
					cout<<i*j%p;
				} else {
					cout<<" "<<i*j%p;
				}
			}
			cout<<endl;
		}
	}
	return 0;
}

hdu6441 Find Integer 【费马大定理】

传送门

复习费马大定理的定义:

当整数n >2时,关于x, y, z的方程 x^n + y^n = z^n 没有正整数解

题意:

题解:

题解来源

AC_code:

#include<bits/stdc++.h>
using namespace std;
int main() {
	int t;
	cin>>t;
	while(t--) {
		int a, n;
		scanf("%d%d", &n, &a);
		if(n > 2 || n == 0){
			printf("-1 -1\n");
		}else if (n == 1){
			printf("%d %d\n",1,a+1);
		}else {
			int b, c;
			if(a % 2){
				b = (a*a-1)/2;
				c = (a*a+1)/2;
				printf("%d %d\n",b, c);
			}else {
				b = (a*a/2-2)/2;
				c = (a*a/2+2)/2;
				printf("%d %d\n",b, c);
			}
		}
	}
	return 0;
}

hdu6446Tree and Permutation【邻接表dfs】

题目链接:传送门

题意:给你一颗树,然后让你求n!种序列中,所以得序列和,序列和定义为:A1,A2,A3……AN=A1A2+A2A3+…….An-1An

题解:经过打表推出一种规律,所有任意每两个点之间的距离之和的(n-1)!倍为答案

那么就要求出每两个点之间的距离,暴力走一遍会tle,于是有一种思路:

对于题目给出的n-1条边,我们可以这样考虑,去掉这条边后,将树分成了两部分,一部分有m个节点,另一部分有(n-m)个节点,所以我们必须在这两块中任意选择一个节点才会进过这条边,那么左边的点到右边的点有m*(n-m)条,即这条边贡献了m*(n-m)次,那么我们只要dfs遍历每条边两边的的点,就可以得出最终的答案。

AC_code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const ll mod = 1e9+7;
struct edge{
	int u,v;
	ll w;
}e[maxn*2];
int head[maxn], num[maxn];
ll node[maxn];
ll ans;
int tot, n;
ll fac[maxn];
void add(int u, int v, int w){
	e[++tot].u = head[u];
	e[tot].w = w;
	e[tot].v = v;
	head[u] = tot;
} 

void init() {
	fac[0] = 1;
	fac[1] = 1;
	for(int i = 2; i < maxn; i++){
		fac[i] = fac[i-1]*i%mod;
	}
}

void dfs(int u, int v) {
	node[u] = 1;
	for(int i = head[u]; i != 0; i = e[i].u){
		int to = e[i].v;
		if(to == v){
			continue;
		}
		dfs(to, u);
		node[u] += node[to];
		ans = (ans + (node[to]*(n-node[to])%mod)*e[i].w%mod)%mod;
	}
}

int main() {
	init();
	while(~scanf("%d", &n)){
		tot = 0;
		memset(head, 0, sizeof(head));
		memset(node, 0, sizeof(node));
		memset(num, 0, sizeof(num));
		for(int i = 1; i < n; i++){
			int u, v;
			ll w;
			scanf("%d%d%lld", &u, &v, &w);
			num[u]++;
			num[v]++;
			add(u, v, w);
			add(v, u, w);
		}
		ans = 0;
		for(int i = 1; i <= n; i++){
			if(num[i] == 1){
				dfs(i, 0);
				break;
			}
		}
		ans = ans*2%mod*fac[n-1]%mod;
		printf("%lld\n",ans);
	}
	return 0;
} 

后续会继续完善题目