4033 - C.直角边

勾股定理，西方称为毕达哥拉斯定理，它所对应的三角形现在称为：直角三角形。

丁丁突然很想知道如果已知直角三角形的一条直角边a是正整数，那么另外两条边也必是正整数的情况会是多少种？为了先简化计算，他想先简化a是奇数的情况，请你帮帮他。

Input

有多行输入（不超过300行）。每一行是一个奇整数a（a<10^7）。

Output

有多行输出，每一行输出一个整数，表示满足条件的直角三角形个数。

Examples

Input

3
15

Output

1
4

Solution C++

//#include "stdafx.h"
#include <string>
//#include <fstream>
#include <algorithm>
#include <vector>
#include <map>
#include <iostream>
#include <time.h>   
#include <cmath>

using namespace std;

const int M = 1e8;
;
const int NN = 1e4;
const int KK = 10000007;

int prime[NN + 1];
int vis[NN + 1] = { 0 };
int nLen = 0;


void findPrime(int N)
{
	int m = (int)sqrt(N + 0.0);

	for (int i = 2; i <= m; i++)
	{
		if (vis[i] == 0)
		{
			for (int j = i*i; j <= m; j += i)
			{
				vis[j] = 1;
			}
		}
	}

	for (int n = 2; n <= m; n++)
	{
		if (vis[n] == 0)
		{
			prime[nLen++] = n;
		}
	}
}




class RunTime
{
	clock_t start, end;
public:
	RunTime()
	{
		start = clock();
	}
	~RunTime()
	{
		end = clock();
		double dur = (double)(end - start);
		printf("Use Time:%f\n", (dur / CLOCKS_PER_SEC));
	}

};

int calcTime(int n, int m, int &times)
{
	times = 0;
	while (n %m == 0)
	{
		times++;
		n /= m;
	}
	return n;
}

int Solve(int n)
{
	int sum = 1;
	int times;
	int k = (int)sqrt(n + 0);
	for (int i = 0; i < nLen; i++)
	{
		if (prime[i] > k)
		{
			break;
		}
		if (n % prime[i] == 0)
		{
			n = calcTime(n, prime[i], times);
			sum = sum * (1 + 2 * times);// % KK;
		}
		if (prime[i] > n)
		{
			break;
		}

	}
	if (n != 1)
		sum *= 3;
	return (sum - 1) / 2;
}


int main()
{
	//ifstream fin("data.txt");//数据都放在data.txt
	//RunTime obj;
	findPrime(M);//找出素数

	//cout << nLen << endl;
	//cout << sizeof(vis) << endl;
	int n, d;

	while (cin >> n)
	{
		d = Solve(n);

		cout << d << endl;
	}


	return 0;
}

Time Limit	1 second
Memory Limit	128 MB

Discuss Stats

上一题下一题