首页 > 代码库 > 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的最大公约数(者)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。