部分数论(补

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,ans=0;
    cin >> n;
    for(long long l=1,r;l<=n;l=r+1){
        r = n/(n/l);            //计算r,让分块右移
        ans += (r-l+1)*(n/l);   //求和
        cout << l <<""<< r <<": "<< n/r << endl;  //打印分块
    }
    cout << ans;               //打印和
}

ll ans=0;
for(ll l=1,r;l<=n;l=r+1)
{
    if(w/l)r=w/(w/l);
    else r=n;
    r=min(r,n);
    ans+=(r-l+1)*(w/l);
}
int prime[N],cnt=0; //prime数组存放所以素数,cnt为素数个数
bool st[N]; //false为素数
int phi[N]; //记录欧拉函数
void get_prime(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]) prime[cnt++]=i,phi[i]=i-1; //把素数i存到prime数组中
        for(int j=0;j<cnt&&i*prime[j]<=n;j++){
            st[i*prime[j]]=true; //找到的素数的倍数不访问
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*phi[prime[j]];
        }
    }
}

高精度gcd(Stein算法)

int stein(int a,int b){
    if(a<b) a^=b,b^=a,a^=b;        //交换,使a为较大数; 
    if(b==0)return a;                    //当相减为零,即两数相等时,gcd=a; 
    if((!(a&1))&&(!(b&1))) return stein(a>>1,b>>1)<<1;   //s1,注意最后的左移,在递归返回过程中将2因子乘上;
    else if((a&1)&&(!(b&1)))return stein(a,b>>1);            //s2;
    else if((!(a&1))&&(b&1))return stein(a>>1,b);
    else return stein(a-b,b);                                             //s3;  
} 

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
2 收藏 评论
分享

全站热榜

正在热议