首页 > 代码库 > 【欧拉函数】BZOJ4173-数学
【欧拉函数】BZOJ4173-数学
【题目大意】
【思路】
基本是popoqqq大爷的题解，稍微添加了几句自己的注释，方便理解
同理，如果n%k+m%k＜k等价于
0
=∑([(n+m)/k]-[n/k]-[m/k])×φ(k) ……因为k不满足条件的时候前面为0
……其实右边两个∑也是k=1..(m+n)，但是k>n的时候，[n/k]显然为0，m同理。
【错误点XXXXD】
……程序烧杯，po也是烧杯。不要忘了ll，不要忘了MOD……
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define MOD 998244353 6 using namespace std; 7 typedef long long ll; 8 9 ll phi(ll x)10 {11 ll ret=x;12 for (ll i=2;i*i<=x;i++)13 {14 if (x%i==0)15 {16 ret-=ret/i;17 while (x%i==0) x/=i;18 }19 }20 if (x>1) ret-=ret/x;21 return ret%MOD;22 }23 24 void solve()25 {26 ll n,m;27 scanf("%lld%lld",&n,&m);28 printf("%lld",(phi(n)%MOD)*(phi(m)%MOD)%MOD*(n%MOD)%MOD*(m%MOD)%MOD); 29 }30 31 int main()32 {33 solve();34 return 0;35 }
【欧拉函数】BZOJ4173-数学
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。