「TJOJ1107」张老师很强

题目描述

张老师最近在看《最强大脑》节目，然后张老师突然发觉自己原来很强！为什么这么说呢，因为张老师发现给他一个很大的正整数 n，他可以一秒找到一个最小正整数 m，使 √n*m为一个正整数。突然发现自己这么强，张老师已经感觉自己已经可以上天了，计算机都没办法跟他肩并肩。所以请同学们帮忙让张老师清醒一点，告诉他计算机也可以轻松做到这件事情。

输入

第一行一个正整数 T (T≤100)
对于每一组数据：
一个正整数 n (n ≤ 2,000,000,000)

输出

对于每一组数据
输出 Case #t:，t表示第 t组数据
一个正整数 m，满足 m是最小的正整数可以使 √n*m为一个正整数。

样例输入

2
2
4

样例输出

Case #1:
2
Case #2:
1

题解

本身是一道十分简单的题目，直接根号 n分解质因数即可。

然而我至今不知道为什么素数表过不了……

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
#define N 5000005
using namespace std;

int t, a, b, tot;

int read()
{
	int x = 0, f = 1; char ch = getchar();
	while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }
	while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
	return x*f;
}

int main()
{
	freopen("a.txt", "r", stdin);
	int ans = 1;
	t = read();
	for (int tt = 1; tt <= t; tt++)
	{
		a = read();
		b = a;
		ans = 1;
		for (int i = 2; i <= sqrt(b); i++)
		{
			int num = 0;
			while (1)
			{
				if (a%i == 0)
				{
					a /= i;
					num++;
				}
				else
					break;
			}
			if (num % 2 == 1)
				ans *= i;
		}
		ans *= a;
		if (b == 1 || b == 2 || b == 3)
			ans = b;
		printf("Case #%d:\n%d", tt, ans);
		if (tt != t)
			printf("\n");
	}
	return 0;
}