部分数论（补

#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;  
}