Luogu P4844 LJJ爱数数
发布日期:2021-05-04 16:55:18
浏览次数:54
分类:技术文章
本文共 2788 字,大约阅读时间需要 9 分钟。
题目链接
题解
1 a + 1 b = 1 c \frac{1}{a}+\frac{1}{b}=\frac{1}{c} a1+b1=c1
即
b c + a c = ( a + b ) c = a b bc+ac=(a+b)c=ab bc+ac=(a+b)c=ab 设 g = gcd ( a , b ) , A = a g , B = b g g=\gcd(a,b),A=\frac{a}{g},B=\frac{b}{g} g=gcd(a,b),A=ga,B=gb,则有 g ( A + B ) c = A B g 2 ( A + B ) c = A B g g(A+B)c=ABg^2\\ (A+B)c=ABg g(A+B)c=ABg2(A+B)c=ABg 由于 c ̸ = 0 , g ̸ = 0 c\not= 0,g\not= 0 c̸=0,g̸=0 A + B g = A B c = k \frac{A+B}{g}=\frac{AB}{c}=k gA+B=cAB=k 假设 k ≥ 2 k\geq 2 k≥2,那么 A B = k c AB=kc AB=kc,由于 gcd ( A , B ) = 1 \gcd(A,B)=1 gcd(A,B)=1,因此 k ∣ A k|A k∣A或 k ∣ B k|B k∣B,不可能同时满足,那么 k ∤ A + B k\nmid A+B k∤A+B,但是 A + B = k g A+B=kg A+B=kg,推出矛盾,因此 k = 1 k=1 k=1。那么
A + B = g , A B = c A+B=g,AB=c A+B=g,AB=c 如果已经得到了 g g g和 A A A,满足题目要求的条件就是 gcd ( A , g − A ) = 1 , ( g − A ) A ≤ n , A g ≤ n , ( g − A ) g ≤ n \gcd(A,g-A)=1,(g-A)A\leq n,Ag\leq n,(g-A)g\leq n gcd(A,g−A)=1,(g−A)A≤n,Ag≤n,(g−A)g≤n 容易发现 gcd ( A , g ) = 1 , 2 ≤ g ≤ 2 n , max ( g − ⌊ n g ⌋ , 1 ) ≤ A ≤ min ( ⌊ n g ⌋ , g − 1 ) \gcd(A,g)=1,2\leq g\leq \sqrt{2n},\max(g-\lfloor\frac{n}{g}\rfloor,1)\leq A\leq \min(\lfloor \frac{n}{g}\rfloor,g-1) gcd(A,g)=1,2≤g≤2n,max(g−⌊gn⌋,1)≤A≤min(⌊gn⌋,g−1) 因此反演求出一段区间内与 g g g互质的数的个数即可。注意这题卡时限,必须预处理出每个数的约数,还要用邻接表存,不能用vector,否则会TLE……
代码
#include#include #include #include template T read(){ T x=0; int f=1; char ch=getchar(); while((ch<'0')||(ch>'9')) { if(ch=='-') { f=-f; } ch=getchar(); } while((ch>='0')&&(ch<='9')) { x=x*10+ch-'0'; ch=getchar(); } return x*f;}const int maxn=1414213;const int maxm=13288457;int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10],pre[maxm+10],now[maxn+10],son[maxm+10],tot;int add(int a,int b){ pre[++tot]=now[a]; now[a]=tot; son[tot]=b; return 0;}int getprime(){ p[1]=mu[1]=1; for(int i=2; i<=maxn; ++i) { if(!p[i]) { prime[++cnt]=i; mu[i]=-1; } for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j) { int x=i*prime[j]; p[x]=1; if(i%prime[j]==0) { mu[x]=0; break; } mu[x]=-mu[i]; } } for(int i=1; i<=maxn; ++i) { if(!mu[i]) { continue; } for(int j=1; j<=maxn/i; ++j) { add(i*j,i); } } return 0;}inline long long solve(int x,int l,int r){ long long ans=0; for(int i=now[x]; i; i=pre[i]) { int k=son[i]; ans+=mu[k]*(r/k-l/k); } return ans;}long long n;int main(){ getprime(); n=read (); long long ans=0; int mx=sqrt(2*n)+0.5; for(int i=2; i<=mx; ++i) { ans+=solve(i,std::max(1ll,i-n/i)-1,std::min(n/i,i-1ll)); } printf("%lld\n",ans); return 0;}
转载地址:https://blog.csdn.net/wang3312362136/article/details/85993442 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
能坚持,总会有不一样的收获!
[***.219.124.196]2024年04月13日 01时37分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
学以致用设计模式 之 “组合模式”
2019-04-27
我用过的设计模式(7)--享元模式
2019-04-27
MySQL数据库从入门到实战应用(学习笔记一)
2019-04-27
MySQL数据库从入门到实战应用(学习笔记二)
2019-04-27
种树:二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林
2019-04-27
【C++】攻克哈希表(unordered_map)
2019-04-27
转:【答学员问】- 该如何根据岗位学习相关技能
2019-04-27
转:【答学员问】有什么经验教训,是你在面试很多次之后才知道的?
2019-04-27
消息队列:解耦、异步、削峰,现有MQ对比以及新手入门该如何选择MQ?
2019-04-27
【奇技淫巧】-- 三角形最小路径和
2019-04-27
【小技巧】argc和argv的用法
2019-04-27
学不下去了怎么办?
2019-04-27
二叉树的前中后序遍历(迭代法)(带动画)
2019-04-27
【小技巧】【XShell】【Xftp】Windows桌面与Linux虚拟机互传文件
2019-04-27
【redis入门】Centos下安装redis
2019-04-27
【redis入门】redis安装后相关知识串讲
2019-04-27
【redis】来吧,展示一下redis 发布-订阅模式
2019-04-27
当下热点词再学:redis缓存预热、更新、降级,限流
2019-04-27