250PT不说了。很水得一题。
500PT
给定n(<=1e18)，求最大的因子，且这个因子为完全平方，假设这个因子为x那么满足x*x*y = n, 一直枚举因子到n^(1/3)就可以了。
最后判断一下剩余的是不是完全平方。
1000PT
一个排列组合题，一个中心出发有k条路，路与路之间有且仅有中心这个交点。现在要建n个城市，编号1~n,使得中心有一个城市，每条路末端有一个城市，然后其余城市就放在各条路的中间。首先保证中心和末端处各建设1个城市，问
总共有多少种安排方式。两种安排方式不同，表示至少存在一个城市他的邻居集合不相同。邻居是指不需要穿过任何城市就能直接到达的。
分析：
首先容易知道，中心城市有k个邻居，位于路的末端的城市有且仅有一个邻居，其他城市必须有2个邻居
所以对这个题目对k值分情况考虑：
k <= 2和k<=1时，由于此时路径可连接起来看做一条直线，实际相当于给n个城市一个排列，而且首尾交换的排列只能算一个，所以答案是n!/2.
k>=3 时，首先选定中心城市，n种情况，然后选定末端城市C(n-1,k)，接下来剩n-k-1个城市，要各自安放在k条路径上，而且是应该考虑安放顺序的，所以是将n-k-1分给k条道路，并且排列一下。n-1-k分给k条道路可以这样理解。在n-1-k个*******中插入k-1条木棍，变成这样**|*|***|**, 在n-1-k+k-1 = n-2中选择k-1根木棍的位置，最后就是(n-k-1)!*C(n-2,k-1),ans = n*C(n-1,k)*(n-k-1)!*C(n-2,k-1) = n!*(n-2)!/(k-1)!/(n-k-1)!/k!.
代码：
//Template update date: 20140316
#include <iostream>
#include <sstream>
#include <cstdio>
#include <climits>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#define esp 1e-6
#define pi acos(-1.0)
#define inf 0x0f0f0f0f
#define pb push_back
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define lowbit(x) (x&(-x))
#define mp(a, b) make_pair((a), (b))
#define in freopen("solve_in.txt", "r", stdin);
#define out freopen("solve_out.txt", "w", stdout); #define bug puts("********))))))");
#define inout in out #define SET(a, v) memset(a, (v), sizeof(a))
#define READ(a, n) {REP(i, n) cin>>(a)[i];}
#define REP(i, n) for(int i = 0; i < (n); i++)
#define Rep(i, base, n) for(int i = base; i < n; i++)
#define REPS(s, i) for(int i = 0; s[i]; i++)
#define pf(x) ((x)*(x))
#define Log(a, b) (log((double)b)/log((double)a))
#define Srand() srand((int)time(0))
#define random(number) (rand()%number)
#define random_range(a, b) (int)(((double)rand()/RAND_MAX)*(b-a) + a) using namespace std; typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<PII> VII;
typedef vector<PII, int> VIII;
typedef VI:: iterator IT;
typedef map<string, int> Mps;
typedef map<int, int> Mpi;
typedef map<int, PII> Mpii;
typedef map<PII, int> Mpiii;
const int maxn = *+;
LL inv[maxn];
const int M = ;
class Byteland{
public:
LL powmod(LL a, LL b, LL M) {
LL res = ;
while(b) {
if(b&) res = (res*a)%M;
a =(a*a)%M;
b >>= ;
}
return res;
} void pre() {
Rep(i, , maxn) {
inv[i] = powmod(i, M-, M);
}
}
LL solve(LL n, LL k) {
pre();
LL ans = ;
if(k <= ) {
Rep(i, , n+) {
ans = (ans*i)%M;
}
ans = ans*powmod(, M-, M)%M;
} else {
Rep(i,, n+) {
if(i <= k+)
ans = (ans*(n-i+))%M;
if(i <= n-)
ans = (ans*i)%M;
if(i <= k)
ans = (ans*powmod(i, M-, M))%M;
if(i <= k-)
ans = (ans*powmod(i, M-, M))%M;
}
}
return ans;
}
int CountDifferentMaps(int n, int k){
return solve(n, k);
}
};