打表找规律（筛素数）-白红宇

打表找规律（筛素数）

阅读量：3951 次

发布时间：2019-05-24

本文共 2078 字，大约阅读时间需要 6 分钟。

This time I need you to calculate the f(n) . (3<=n<=1000000)

f(n)= Gcd(3)+Gcd(4)+…+Gcd(i)+…+Gcd(n).

Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1])

C[n][k] means the number of way to choose k things from n some things.

gcd(a,b) means the greatest common divisor of a and b.

Input

There are several test case. For each test case:One integer n(3<=n<=1000000). The end of the in put file is EOF.

Output

For each test case:

The output consists of one line with one integer f(n).

Sample Input

Sample Output

337556486

【打表找规律】

打表找规律，

Gcd(n)=gcd(C[n][1],C[n][2],……,C[n][n-1])

n = 3 res = 3

n = 4 res = 2

n = 5 res = 5

n = 6 res = 1

n = 7 res = 7

n = 8 res = 2

n = 9 res = 3

n = 10 res = 1

n = 11 res = 11

n = 12 res = 1

n = 13 res = 13

n = 14 res = 1

n = 15 res = 1

n = 16 res = 2

n = 17 res = 17

n = 18 res = 1

n = 19 res = 19

n = 20 res = 1

n = 21 res = 1

n = 22 res = 1

n = 23 res = 23

n = 24 res = 1

n = 25 res = 5

n = 26 res = 1

n = 27 res = 3

n = 28 res = 1

容易看出当n为素数时，结果为，当n只有一个素因子时，结果为该素因子，当n有两个以上包括两个素因子时，结果为1

然后预处理一下，输出就好了

打表代码，才知道求组合数可以用杨辉三角。。。。

#include 
   
    using namespace std;typedef long long LL;LL INF = 1000000000;const LL MAX = 1e6 + 50; LL gcd(LL a, LL b) {    return b ? gcd(b, a%b) : a;}LL Triangle[1000][1000]; void YangHui() {  //杨辉三角求组合数    memset(Triangle, 0, sizeof(Triangle));    for (LL i = 1; i <= 100; ++i) {        Triangle[i][0] = Triangle[i][i] = 1;        for (LL j = 1; j < i; ++j){            Triangle[i][j] = Triangle[i-1][j-1] + Triangle[i-1][j];        }    }}  int main(){    LL n;    YangHui();    //freopen("out.txt", "w", stdout);    while(1){        scanf("%I64d", &n);        LL ans = Triangle[n][1];            for(LL i = 2; i < n; i++){            ans = gcd(ans, Triangle[n][i]);        }         printf("n = %I64d res = %I64d\n", n, ans);    }    return 0;}

AC代码：

#include 
   
    #include 
    
     #include 
     
      using namespace std;const int maxn=1000000+50;typedef long long ll;ll vis[maxn];//判断出现ll cnt[maxn];//记录素因子个数ll num[maxn];//记录最大素因子void prime(){    for(int i=2;i
      
       >n)    {        cout<
       
        <