3557513_ac_3563ms_320k.cc

北大大牛代码 1240道题的原代码 超级权威

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int N, no, num[100], c[100];
int ans;
int used[101];

void calc(int n)
{
	int i, q;

	no = 0;
	memset(num,0,sizeof(num));
	if (n % 2==0)
	{
		c[no] = 2;
        while (n%2==0)
        {
			n /= 2;
            num[no]++;
		}
		no++;
	}
	q = (int)sqrt(n) + 1;
    for (i = 3; i < q && n != 1; i+=2)
	{
		if (n%i==0)
		{
			c[no] = i;
            while (n % i == 0)
			{
				n /= i;
                num[no]++;
			}
			q = (int)sqrt(n)+1;
            no++;
		}
	}
	if (n != 1)
    {
		c[no] = n;
        num[no]++;
        no++;
	}
}

void solve()
{
	int i;
	int tmp = 1, Tmp = 1;

	for (i = 0; i < no; i++)
	{
		tmp *= used[i] + 1;
		Tmp *= num[i] - used[i] + 1;
	}
	ans += tmp * tmp * tmp + Tmp * Tmp * Tmp;
}

void dfs(int l,int p)
{
	int i, t;

	if(l==no)
	{
		solve();
		return ;
	}
	t = 1;
	for(i = 0; i <= num[l]; i++)
	{
		used[l] = i;
		dfs(l + 1, p * t);
		t *= c[l];
	}
}

int main()
{
	int cas;

	scanf("%d", &cas);
	while (cas-- > 0)
	{
		scanf("%d", &N);
		calc(N);
		ans = 0;
		dfs(0, 1);
		memset(used, 0, sizeof(used));
		printf("%d\n", ans / 2);
	}
	return 0;
}