Find Integer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 6597    Accepted Submission(s): 1999
Special Judge

Problem Description

people in USSS love math very much, and there is a famous math problem .

give you two integers n,a,you are required to find 2 integers b,c such that an+bn=cn.

 

Input

one line contains one integer T;(1≤T≤1000000)

next T lines contains two integers n,a;(0≤n≤1000,000,000,3≤a≤40000)

 

Output

print two integers b,c if b,c exits;(1≤b,c≤1000,000,000);

else print two integers -1 -1 instead.

 

Sample Input

1
2 3

 

Sample Output

4 5

题解：费马大定理，又被称为“费马最后的定理”，它断言当整数n >2时，关于x, y, z的方程 x^n + y^n = z^n 没有正整数解。

本题是费马大定理：n>2时无解，n=0时，无解；n=1时，构造两个数使得a+b=c；n=2时，构造勾股数a*a+b*b=c*c。
 

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int main()
 5 {
 6     int t,n,a;
 7     scanf("%d",&t);
 8     while(t--)
 9     {
10         scanf("%d %d",&n,&a);
11         if(n>2||n==0)
12             printf("-1 -1
");
13         else if(n==1)
14             printf("1 %d",a+1);
15         else
16         {
17             if(a%2)
18             {
19                 int n = (a-1)/2;
20                 int b = 2*n*n+2*n;
21                 int c = b+1;
22                 printf("%d %d
",b,c);
23             }else
24             {
25                 int n = a/2;
26                 int b = n*n-1;
27                 int c = b+2;
28                 printf("%d %d
",b,c);
29             }
30         }
31     }
32     return 0;
33 }

Tree and Permutation

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3086    Accepted Submission(s): 816

Problem Description
There are N vertices connected by N−1 edges, each edge has its own length.
The set { 1,2,3,…,N } contains a total of N! unique permutations, let’s say the i-th permutation is Pi and Pi,j is its j-th number.
For the i-th permutation, it can be a traverse sequence of the tree with N vertices, which means we can go from the Pi,1-th vertex to the Pi,2-th vertex by the shortest path, then go to the Pi,3-th vertex ( also by the shortest path ) , and so on. Finally we’ll reach the Pi,N-th vertex, let’s define the total distance of this route as D(Pi) , so please calculate the sum of D(Pi) for all N! permutations.
 

Input
There are 10 test cases at most.
The first line of each test case contains one integer N ( 1≤N≤105 ) .
For the next N−1 lines, each line contains three integer X, Y and L, which means there is an edge between X-th vertex and Y-th of length L ( 1≤X,Y≤N,1≤L≤109 ) .
 

Output
For each test case, print the answer module 109+7 in one line.
 

Sample Input

3
1 2 1
2 3 1
3
1 2 1
1 3 2

 

Sample Output

16
24
 
题意：求树的任意两点最短距离和的两倍。
题解：树状DP先求解树的任意两点距离和。
我们可以对每条边，求所有可能的路径经过此边的次数：设这条边两端的点数分别为A和B，那 么这条边被经过的次数就是A*B，它对总的距离和的贡献就是(A*B*此边长度)。我们把所有边的贡献求总和，再除以总路径数N*(N-1)/2，即为最 后所求。

每条边两端的点数的计算，实际上是可以用一次dfs解决的。任取一点为根，在dfs的过程中，对每个点k记录其子树包含的点数（包括其自身），设点数为a[k]，则k的父亲一侧的点数即为N-a[k]。这个统计可以和遍历同时进行。故时间复杂度为O(n)。

参考博客：https://www.cnblogs.com/shuaihui520/p/9537214.html