数论专题hdu2582

 

   本题题意:给出公式f(n) = gcd(3) + ... + gcd(n),而gcd(n) = gcd(C(1,n),...,C(n-1,n)),求出f(n)的值。

   代码如下:

   

#include <iostream>
using namespace std;
typedef long long ll;
const int Max = 1000000;
int prime[Max+1];
ll sum[Max+1];
void Prime(){

    int t = 2;

    ll i;

    while(t <= Max){

        for(i=t;i<=Max;i+=t){prime[i] = 1;}

        for(i=t;i<=Max;i*=t){prime[i] = t;}

        for(i=t;i<=Max;i++){

            if(prime[i] == 0){

                t = i;

                break;

            }

        }

        if(i == Max+1){

            break;

        }

    }

}

void Sum()
{

    sum[3] = 3;

    for(int i=4;i<=Max;i++){

        sum[i] = sum[i-1] + prime[i];

    }

}
int main()
{

    Prime();

    Sum();

    int n;

    while(cin >> n){

        cout << sum[n] << endl;

    }    

    return 0;

}

通过打表发现当为p^k形式时(p为素数),gcd(n) = p,否则 gcd(n) = 1,然后就筛下素数,计算下和,结果就出来了。

不过需要注意的是不用long long会flow。

时间: 09-15

数论专题hdu2582的相关文章

数论专题总结

数论专题总结 kuangbin带你飞之数论基础专题已经刷的差不多了,剩下三道一道中国剩余定理一道离散对数还有一道模拟,模拟那道应该是不会去做了,离散对数的那道看了很多题解一直没有理解题目的思路,只能先暂时放放了,中国剩余定理那道是刘汝佳大白书的例题,暂时没思路也只能先放放了,以后有机会再看下大白书,中国剩余定理已经了解了,离散对数的BSBS模版也有了,虽然这两道变形题暂时不会,但是数论专题部分基础已经有一些了,刷该专题的目标已经完成了,下一专题:kmp. 待补充......

数论专题hdu2197

本题题意:求长度为n的本元串的个数,本元串就是无法由几个相同的子串拼接的01串. 代码如下: #include <iostream> using namespace std; typedef long long ll; const int mod = 2008; ll pow_(ll a,ll b,ll mod){ ll sum = 1; while(b){ if(b&1){ sum = sum * a % mod; } a = a * a % mod; b >>= 1;

数论专题测试——幸运数字

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 using namespace std; 7 typedef long long int64; 8 int64 L; 9 int ca; 10 int64 phi(int64 x){ 11 int64 t=x; 12 for (int6

数论专题hdu2104

本题题意:有N个人,一个人从1开始走,每次间隔M-1个人,问他是否能走到所有的点,并回到原点. 代码如下: #include <cstdio> using namespace std; int gcd(int a,int b) { int r; while(b) { r = a % b; a = b; b = r; } return a; } int main(){ int m,n; while(~scanf("%d%d",&m,&n) &&

数论专题测试——逆元

题意:给定n,m,令k=1+sigam(inv(i,n))mod 1000000007.   n,m小于等于10^7. 求k^k^k^k....后一个k是前一个k的指数,  求这个值对m的mod,知道指数循环节,这就是个傻逼题,然而考场就是不知道这个,少了点东西,所以出题人就是个傻逼.... 指数循环节:a^b%c=>a^(b%phi(c)+phi(c))   %c (b>=phi(c)). 这个题b永远无限大,就可以使用,可以考虑预处理出10^7范围内的phi,然后递归,当c==1时,返回0

ACM:数论专题(3)——约瑟夫问题

(p.s: 以前做约瑟夫问题都是用链表模拟,今天发现了一个效率更高的方法,受教了...) 题目描述: 小Hi和小Ho的班级正在进行班长的选举,他们决定通过一种特殊的方式来选择班长. 首先N个候选人围成一个圈,依次编号为0..N-1.然后随机抽选一个数K,并0号候选人开始按从1到K的顺序依次报数,N-1号候选人报数之后,又再次从0开始.当有人报到K时,这个人被淘汰,从圈里出去.下一个人从1开始重新报数. 也就是说每报K个数字,都会淘汰一人.这样经过N-1轮报数之后,圈内就只剩下1个人了,这个人就作

数论专题---除法表达式之高精度运算,扩展欧几里得算法

[题意描述] 给定这样一个表达式:X1/X2/X3/·····/Xk,其中Xi是正整数.除法表达式应到按照从左到右的顺序求和.但在表达式中嵌入括号可以改变计算顺序.输入表达式,判断是否可以通过加括号使得表达式最后的值为整数. [分析] 表达式可以写成E=(X1·X3·····Xk)/X2:(X1一定在分子位置,X2一定在分母位置,其它任意) 问题变为E是否为整数. 对于大数相乘,我们可以采用两种方法避免数据溢出: 1.采用素数的唯一分解定理:存储可能存在素数的个数(如何存储,用一个数组就行) 2

数论之拓展欧几里得求解不定方程和同余方程组(一)

今天接到scy的压缩包,开始做数论专题.那今天就总结一下拓展欧几里得求解不定方程和同余方程组. 首先我们复习一下欧几里得算法: 1 int gcd(int a,int b){ 2 if(b==0) return a; 3 return gcd(b,a%b);4 } 拓展欧几里得算法: 推导过程: 给出A和B,求它们的最大公约数,并且求出x和y,满足Ax+By=gcd(A,B). 当A=0时,x=0,y=1; 当A>0时, 因为exgcd(A,B,x,y)表示Ax+By=gcd(A,B) 而且ex

高斯消元法(Gauss Elimination)【超详解&amp;模板】

高斯消元法,是线性代数中的一个算法,可用来求解线性方程组,并可以求出矩阵的秩,以及求出可逆方阵的逆矩阵.高斯消元法的原理是:若用初等行变换将增广矩阵 化为 ,则AX = B与CX = D是同解方程组. 所以我们可以用初等行变换把增广矩阵转换为行阶梯阵,然后回代求出方程的解. 1.线性方程组 1)构造增广矩阵,即系数矩阵A增加上常数向量b(A|b) 2)通过以交换行.某行乘以非负常数和两行相加这三种初等变化将原系统转化为更简单的三角形式(triangular form) 注:这里的初等变化可以通过