2045: 双亲数

2045: 双亲数

Time Limit: 10 Sec  Memory Limit: 259 MB

Submit: 659  Solved: 302

[Submit][Status][Discuss]

Description

小D是一名数学爱好者,他对数字的着迷到了疯狂的程度。 我们以d = gcd(a, b)表示a、b的最大公约数,小D执著的认为,这样亲密的关系足可以用双亲来描述,此时,我们称有序数对(a, b)为d的双亲数。 与正常双亲不太相同的是,对于同一个d,他的双亲太多了 >_< 比如,(4, 6), (6, 4), (2, 100)都是2的双亲数。 于是一个这样的问题摆在眼前,对于0 < a <= A, 0 < b <= B,有多少有序数对(a, b)是d的双亲数?

Input

输入文件只有一行,三个正整数A、B、d (d <= A, B),意义如题所示。

Output

输出一行一个整数,给出满足条件的双亲数的个数。

Sample Input

5 5 2

Sample Output

3 【样例解释】 满足条件的三对双亲数为(2, 2) (2, 4) (4, 2)

HINT

对于100%的数据满足0 < A, B < 10^ 6

Source

第一届“NOIer”全国竞赛

题解:基本上同BZOJ2301,就是大大弱化了= =

 1 /**************************************************************
 2     Problem: 2045
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:1448 ms
 7     Memory:11944 kb
 8 ****************************************************************/
 9  
10 const maxn=1500000;
11 var
12    i,j,k,l,m,n,x1,y1,x2,y2,z:longint;
13    a,b:array[0..maxn] of longint;
14 procedure swap(var x,y:longint);
15           var z:longint;
16           begin
17                z:=x;x:=y;y:=z;
18           end;
19 function doit(x,y:longint):int64;
20          var i,j,k:longint;
21          begin
22               doit:=0;
23               if x>y then swap(x,y);
24               if x=0 then exit(0);
25               i:=1;
26               while i<=x do
27                     begin
28                          if (x div (x div i))<(y div (y div i)) then
29                             k:=x div (x div i)
30                          else k:=y div (y div i);
31                          inc(doit,(b[k]-b[i-1])*int64(x div i)*int64(y div i));
32                          i:=k+1;
33                     end;
34          end;
35 begin
36      for i:=2 to maxn do
37          begin
38               if a[i]<>0 then continue;
39               for j:=i to maxn div i do a[i*j]:=i;
40          end;
41      b[1]:=1;
42      for i:=2 to maxn do
43          if a[i]=0 then b[i]:=-1 else
44             if ((i div a[i]) mod a[i])=0 then b[i]:=0 else
45                b[i]:=-b[i div a[i]];
46      for i:=2 to maxn do b[i]:=b[i]+b[i-1];
47      readln(n,m,l);
48      writeln(doit(n div l,m div l));
49      readln;
50 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2301: [HAOI2011]Problem b

    2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MB Submit: 1737...

    HansBug
  • 3211: 花神游历各国

    3211: 花神游历各国 Time Limit: 5 Sec  Memory Limit: 128 MB Submit: 1042  Solved: 381 ...

    HansBug
  • 1257: [CQOI2007]余数之和sum

    1257: [CQOI2007]余数之和sum Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2001  So...

    HansBug
  • H5页面实现原理分析

    <!doctype html> <html> <head> <style> html{overflow:hidden;} body{margin:0;} .w...

    用户1730674
  • jquery选择器

    jquery选择器可以快速地选择元素,选择规则和css样式相同,使用length属性判断是否选择成功。

    Devops海洋的渔夫
  • 解决bootstrap row span设置border换行的问题

    版权声明:本文为[他叫自己Mr.张]的原创文章,转载请...

    他叫自己MR.张
  • flex 布局

    CSS3 为我们提供了一种可伸缩的灵活的 web 页面布局方式 flexbox 布局,它具有很强大的功能,可以很轻松实现很多复杂布局。可以简便、完整、响应式地实...

    Krry
  • 原生JS实现拖拽鼠标绘画

    越陌度阡
  • 前端-part8-jQurey操作样式一:获取标签属性+修改标签属性

    少年包青菜
  • selenium-java web自动化测试工具

    本篇文章由来,这两天整理了下自己经常使用而且很熟练的项目,今天突然想起漏了一个,补上了,但想到还没对应的博客,那就写一个简单的

    肖哥哥

扫码关注云+社区

领取腾讯云代金券