首页 > 代码库 > T7316 yyy的最大公约数(者)

T7316 yyy的最大公约数(者)

题目背景

全场基本暴力

题目描述

技术分享

输入输出格式

输入格式:

 

如图

 

输出格式:

 

如图

 

输入输出样例

输入样例#1:
如图
输出样例#1:
如图

说明

如图

 

 

这题用到了容斥原理和线性筛的一些东西,

表示没怎么看懂、。。。

 

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<queue> 7 #include<stack> 8 #include<cstdlib> 9 #define lli long long int 10 using namespace std;11 const int mod = 998244353;12 const lli maxn=0x7fffff;13 14 const lli MAXN=10000001;15 inline void read(lli &n)16 {17     char c=+;lli x=0;bool flag=0;18     while(c<0||c>9){c=getchar();if(c==-)flag=1;}19     while(c>=0&&c<=9)20     x=(x<<1)+(x<<3)+c-48,c=getchar();21     flag==1?n=-x:n=x;22 }23 lli n,m;24 lli ans=0;25 lli now[MAXN];26 int main()27 {28     read(n);29     read(m);30     if(n>m)31         swap(n,m);32         33     for(lli i=n;i>=1;i--)34     {35         now[i]=1ll*(n/i)*(m/i);36         for(lli j=i+i;j<=n;j+=i)37             now[i]-=now[j];38         ans+=now[i]*i;39     }40     printf("%lld",ans%mod);41     return 0;42 }

 

T7316 yyy的最大公约数(者)