首页 > 其他 > 详细

D - Send a Table (UVA - 10820)

时间:2018-02-14 15:27:22      阅读:119      评论:0      收藏:0      [点我收藏+]

标签:存储   names   long long   ems   cst   int   nbsp   两个   cstring   

- 题目大意

     给出一个n,求从1~n中任意两个数互质的对数为多少,(a,b)和(b,a)算两对。

- 解题思路

    构造一个欧拉函数的方法,然后用一个数组去存储下标,因为(a,b)和(b,a)算两对,所以每一个都加两倍,但(1,1)很特殊,所以最后减一就行了。

- 代码

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
const int MAX = 600000;

int phi[MAX];
void find()
{
	memset(phi, 0, sizeof(phi));
	for (int i = 1; i < MAX; i++) phi[i] = i;
	for (int i = 2; i < MAX; i++) {
		if (phi[i] == i) {
			for (int j = i; j < MAX; j += i) {
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
}
int main()
{
	int x;
	int q = 600;
	find();
	phi[1] = 1;
	while (q--)
	{
		cin >> x;
		long long sum = 0;
		if (x == 0)
			break;
        for (long long i = 1; i <= x; i++)
				{
					sum += phi[i];
				}	
	cout << 2*sum-1 << endl;
	}
return 0;
}

  

 

D - Send a Table (UVA - 10820)

标签:存储   names   long long   ems   cst   int   nbsp   两个   cstring   

原文:https://www.cnblogs.com/alpacadh/p/8448350.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号