记录编号	531969	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[UVA 11426] [济南集训 2017] 求gcd之和	最终得分	100
用户昵称	真香警告	是否通过	通过
代码语言	C++	运行时间	8.650 s
提交时间	2019-05-22 15:52:31	内存使用	242.54 MiB

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
/*
特性 :
1.若a为质数,phi[a]=a-1;
2.若a为质数,b mod a=0,phi[a*b]=phi[b]*a
3.若a,b互质,phi[a*b]=phi[a]*phi[b](当a为质数时,if b mod a!=0 ,phi[a*b]=phi[a]*phi[b])
*/
const int n=10000010;
const int mod=998244353;
long long a,b;
long long m[n],phi[n],p[n],nump;
//m[i]标记i是否为素数,0为素数,1不为素数;p是存放素数的数组;nump是当前素数个数;phi[i]为欧拉函数
int main()
{
	freopen("hoip.in", "r", stdin);  
    freopen("hoip.out", "w", stdout); 
    phi[1]=1;
    for (int i=2;i<=n;i++)
    {
        if (!m[i])//i为素数
        {
            p[++nump]=i;//将i加入素数数组p中
            phi[i]=i-1;//因为i是素数,由特性得知    
        }    
        for (int j=1;j<=nump&&p[j]*i<=n;j++)  //用当前已得到的素数数组p筛,筛去p[j]*i
        {
            m[p[j]*i]=1;//可以确定i*p[j]不是素数 
            if (i%p[j]==0) //看p[j]是否是i的约数,因为素数p[j],等于判断i和p[j]是否互质 
            {
                phi[p[j]*i]=phi[i]*p[j]%mod; //特性2
                break;
            }
            else phi[p[j]*i]=phi[i]*(p[j]-1)%mod; //互质,特性3其,p[j]-1就是phi[p[j]]   
        }
    }
    cin>>a>>b;
    int minn;
    minn=min(a,b);
    int ans=0;
    for(int i=1;i<=minn;i++){
		ans+=(phi[i]%mod+mod)%mod*(a/i)%mod*(b/i)%mod;
		
		if(ans>=mod)ans-=mod;
	}
	cout<<ans<<endl;
    return 0;
}