传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2005
题解:
设f[i]表示gcd(x,y)=i 的个数(1<=x<=n,1<=y<=m),那么最后的结果就是,其中n=min(n,m)。
那么现在关键就是求解f[i]了。其中gcd(x,y)=i的倍数为[n/i]*[m/i],但是这个包括了i的倍数,所以-2i-3i-……。
为了避免算术,我们逆过来求就行了。
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;
#define si1(a) scanf("%d",&a)
#define si2(a,b) scanf("%d%d",&a,&b)
#define sd1(a) scanf("%lf",&a)
#define sd2(a,b) scanf("%lf%lf",&a,&b)
#define ss1(s) scanf("%s",s)
#define pi1(a) printf("%d\n",a)
#define pi2(a,b) printf("%d %d\n",a,b)
#define mset(a,b) memset(a,b,sizeof(a))
#define forb(i,a,b) for(int i=a;i<b;i++)
#define ford(i,a,b) for(int i=a;i<=b;i++)
typedef long long LL;
const int N=100005;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-7;
LL f[N];
int main()
{
LL n,m;
while(cin>>n>>m)
{
mset(f,0);
if(n>m) swap(n,m);
LL sum=0;
for(LL i=n;i>=1;i--)
{
f[i]=(n/i)*(m/i);
for(int j=i+i;j<=n;j+=i)
f[i]-=f[j];
sum+=f[i]*(2*i-1);
}
cout<<sum<<endl;
}
return 0;
}
分享到:
相关推荐
OJ系统汇总-2021-10-5.pdf
OJ系统汇总-2021-10-5(C)-32页.pdf
OJ系统汇总-2021-10-5(B).pdf
OJ系统汇总-2021-10-6(C)-32页.pdf
OJ系统汇总-2021-12-24(d).pdf
为了获知基因序列在功能和结构上的相似性,经常需要将几条不同序列的DNA进行比对,以判断该比对的DNA是否具有相关性。 现比对两条长度相同的DNA序列。首先定义两条DNA序列相同位置的碱基为一个碱基对,如果一个碱基...
OJ-Data-Structures-and-Algorithms:上海交通大学
官方离线安装包,亲测可用
leetcode ...oj Shun_LeetCode_OJ_Solutions 这是我在 LeetCode Online Judge 挑战中的代码库。 所有解决方案均为原创,任何人都可以自由使用。 如果您对我如何解决特定问题有任何疑问,请随时与我联系。
leetcode 和 oj 我的 OJ 解决方案 这个存储库包含了我的问题解决方案,来自 ,和望岛书。 目前无法访问。 使用 GCC 7.2.0。
登录ssh,执行安装脚本:wget http://dl.hustoj.com/install-ubuntu-bt.shsudo bash install-ubu
NOI2012年第一场题目+数据,导入hustoj可用
leetcode 和 oj 设计-搜索-自动完成-系统 受 Leetcode OJ 启发: 为搜索引擎设计一个搜索自动完成系统...现在,用户想要输入一个新句子。 以下函数将提供用户键入的下一个字符: List input(char c):输入c是用户输入的
我09年参加现场赛前准备的,这些公式有的是在POJ等OJ上做题时遇到的,还有些可能会出现的数学公式,本人非数学出身,准备的内容尚浅,就是多和乱(不敢说丰富)
oj 力码 一些基于 Java 的有趣的 OJ 实践。 主要来自 LeetCode,部分来自 LintCode 和 Google OJ。 细绳 - 添加二进制 大批 - 计数位-第三个最大数量 堆栈和堆 -解码字符串- 在每个树行中找到最大值- 最小堆栈 树 -...
oj LeetCode-OJ 问题 # 标题 困难 标签 0233 数字一 中等的 数学 0229 多数元素 II 中等的 大批 0224 基本计算器 中等的 数学/堆栈 0216 组合和III 中等的 数组/回溯 0209 最小尺寸子阵列总和 中等的 数组/两个指针/...
oj 算法虐我千百遍,我待算法如初恋 这里的内容是我学习算法过程的一些记录,希望能一直坚持下去。 学习方法 把所有经典算法写一遍 看算法有关源码 看经典书籍 刷题 基本数据结构和算法 这些算法全部自己敲一遍: ...
oj leetcode-1-Two-Sum 这是我在 Github 的第一天。 我只是 AC leetcode 中的第一个问题。 从现在开始,我将使用Github在leetcode中记录我的生活。 我擅长 C++,但对 java 和 Python 不是很专业,我将使用最流行的 3...
BJFU-OJ实验
oj 程序员应该访问的 TOP 网站 一些对程序员有用的网站。 在学习 CS 时,您必须了解一些有用的网站,以便随时了解如何更好地使用您的技术并学习新事物。 这是您应该访问的一些网站的非详尽列表。 此列表将在我获得另...