T287328 求和（正经题目）（有数据） 题解

题目

30分 暴力：

#include<bits/stdc++.h>
#define for1(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
using namespace std;
ll  gcd(ll a,ll b)
{
	if(b==0) return a;
	return gcd(b,a%b);
}
ll n,k,ans;
int main()
{
//	freopen("data3.in","r",stdin); 
//	freopen("data3.out","w",stdout); 
	cin>>n>>k;
	for1(i,1,n) 
	{
		ans+=gcd(i,k);
	}
	cout<<ans<<endl;
	return 0;
 } 

100 分 找到k的每个因子，然后容斥计算一下：

#include<bits/stdc++.h>
#define for1(i,a,b) for(ll i=a;i<=b;i++)
#define ll long long
using namespace std;
ll n,k,cnt;
ll jl[500005],ans;
struct node{
	ll x;
	ll y;
}a[500005];

bool cmp(node x,node y)
{
	return x.x<y.x;
}
int main()
{
//	freopen("data10.in","r",stdin); 
//	freopen("data10.out","w",stdout); 
	cin>>n>>k;
	for1(i,1,sqrt(k))
	{
		if(k%i==0)
		{
		a[++cnt].x=i;
		a[cnt].y=n/i;
		
		a[++cnt].x=k/i;
		a[cnt].y=n/(a[cnt].x);
		}
	}
	sort(a+1,a+cnt+1,cmp);
	for(int i=cnt;i>=1;i--)
	{
		
		for1(j,1,i-1)
		{
			if(a[i].x%a[j].x==0) a[j].y-=a[i].y;
		}
	}
	for1(i,1,cnt)
	    ans+=a[i].x*a[i].y;
	cout<<ans<<endl;
	return 0;
} 

120分 __int128/高精：

#include<bits/stdc++.h>
#define for1(i,a,b) for(ll i=a;i<=b;i++)
#define ll long long
using namespace std;
__int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

__int128 n,k,cnt;
__int128 jl[5000005],ans;
struct node{
	__int128 x;
	__int128 y;
}a[5000005];

bool cmp(node x,node y)
{
	return x.x<y.x;
}
int main()
{
//	freopen("data12.in","r",stdin); 
//	freopen("data12.out","w",stdout); 
	n=read();
	k=read();
	ll ji=k;
	for1(i,1,sqrt(ji))
	{
		if(k%i==0)
		{
		a[++cnt].x=i;
		a[cnt].y=n/i;
		
		a[++cnt].x=k/i;
		a[cnt].y=n/(a[cnt].x);
		}
	}
	sort(a+1,a+cnt+1,cmp);
	for(int i=cnt;i>=1;i--)
	{
		
		for1(j,1,i-1)
		{
			if(a[i].x%a[j].x==0) a[j].y-=a[i].y;
		}
	}
	for1(i,1,cnt)
	    ans+=a[i].x*a[i].y;
	print(ans);
	return 0;
}