T7316 yyy的最大公约数(者)

2018-06-17 22:12:45来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目背景

全场基本暴力

题目描述

输入输出格式

输入格式:

 

如图

 

输出格式:

 

如图

 

输入输出样例

输入样例#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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P2915 [USACO08NOV]奶牛混合起来Mixed Up Cows

下一篇:05:登月计划