ACM刷题之路（二十）线筛素数+找规律f(n) 2019暑期集训 HDU 2585

àì夳堔傛蜴生んèń 2024-02-19 20:39 53阅读 0赞

[题目链接：传送门][Link 1]

感谢此大佬的博客：[https://blog.csdn.net/codeswarrior/article/details/81263050][https_blog.csdn.net_codeswarrior_article_details_81263050] 写的非常好！

**题意：**

给出公式Gcd(n)=gcd(C(n,1),C(n,2),……,C(n,n-1)

其中C(n,1)代表组合C，n选1，等于n！/1！/(n-1)!

让求f(n)=Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n)

输入N，求f(n)

**分析：**

最暴力的做法，就是写一个组合计算函数F(c)，依次把1到100W的gcd算出来.......

暴力终究是暴力，不能解决一切，参考了别人的博客，仔细推理了一下，还真成立

对于G=gcd(C(n,1),C(n,2)，C(n,3)...C(n,n-1) )来说

**有且仅有以下三种情况：**

**(1) 如果n为素数，G=nG=n**

**(2) 如果n有两个或两个以上的素因子，G=1G=1**

**(3) 如果n只有一个素因子pp，G=p**

证明过程见上面博客。

我们先把1到100W的素数筛选出来，放入prime数组，也顺带放入isprime数组可以方便后续o(1)判断是否素数

有几点需要注意的地方：

**1.输入N>=3，不需要考虑小于3的数。**

**2.判断素因子个数的时候，没有从i=2开始到sqrt(x)，而是从prime素数堆中遍历，大大的省时。这点我刚开始没想到**

**3.if (sum == 1 && x == 1)代表素因子唯一**

**(sum == 1 && x > 1)代表素因子不唯一**

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    bool isprime[1000010];
    int prime[100000], len;
    long long fx[1000001];
    int dd(int x) {
    	int sum = 0;
    	int cnt = -1;
    	for (int i = 0; i < len && prime[i] * prime[i] <= x; i++) {
    		if (x % prime[i] == 0) {
    			cnt = prime[i];
    			sum++;
    			if (sum > 1) return 1;
    			while (x % prime[i] == 0) {
    				x /= prime[i];
    			}
    		}
    	}
    	if (sum == 1 && x == 1) return cnt;
    	if (sum == 1 && x > 1) return 1;
    	return 1;
    }
    void init() {
    	memset(isprime, true, sizeof(isprime));
    	len = 0;
    	for (int i = 2; i < 1000001; i++) {
    		if (isprime[i]) {
    			prime[len++] = i;
    			for (int j = i + i; j <= 1000001; j += i) {
    				isprime[j] = false;
    			}
    		}
    	}
    	fx[2] = 0;
    	for (int i = 3; i <= 1000000; i++) {
    		if (isprime[i]) fx[i] = fx[i - 1] + i;
    		else fx[i] = fx[i - 1] + dd(i);
    	}
    }
    int main()
    {
    	init();
    	int n;
    	while (~scanf_s("%d", &n)) {
    		printf("%lld\n", fx[n]);
    	}
    	return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=2582
[https_blog.csdn.net_codeswarrior_article_details_81263050]: https://blog.csdn.net/codeswarrior/article/details/81263050