第n层有多少个n？(Solved)

lulijie

假设第一行为a，b
那么第N行，首尾之间的所有数都可表示为i*a+j*b，   i、j为正整数
    且  当i<=N，j<=N时，所有满足i和j互质的 i*a+j*b 值都存在，所有i和j不互质的 i*a+j*b 值都不存在。
----------------------------------------
当a=b=1，N=2009时，就是楼主的例子：
也就是求满足    i+j=2009，i、j为小于2009的正整数 且 i和j互质 的所有组合数。
    i=1，j=2008
    i=2，j=2007
    i=3，j=2006
    ......
    i=2007，j=2
    i=2008，j=1
因为2009=7*7*41
当i为7的倍数时，j也为7的倍数，i与j不互质，所以i不能等于7的倍数，
当i为41的倍数时，j也为41的倍数，i与j不互质，所以i不能等于41的倍数，
所以所求的总可能数为2008-（2009/7-1）-(2009/41-1)+(2009/(7*41)-1)=2008-286-48+6=1680

lulijie

对于N，假设N的第i个因数为ai，指数为ki
那么，总的个数=N-1- ∑(N/ai-1) + ∑(N/(ai*aj)-1) - ∑(N/(ai*aj*av)-1)+......
若N为素数，那么总的个数=N-1+（1-1）=N-1
N=3，那么总的个数=2-（1-1）=2
N=4，那么总的个数=3-（4/2-1）=2
N=5，那么总的个数=4-（1-1）=4
N=6，那么总的个数=5-（6/2-1)-(6/3-1)+(6/6-1)=5-2-1+0=2
N=8，那么总的个数=7-（8/2-1)=7-3=4
N=30,那么总的个数=29-（30/2-1)-（30/3-1)-（30/5-1)+(30/6-1)+(30/10-1)+(30/15-1)-(1-1)=29-14-9-5+4+2+1=8   
化简  N-1- ∑(N/ai-1) + ∑(N/(ai*aj)-1) - ∑(N/(ai*aj*av)-1)+......
       应该得到金眼睛的计算公式。

[ 本帖最后由 lulijie 于 2009-6-28 13:10 编辑 ]

ggglgq

　　
　　
  
    好主题！
  
      
     a                                                                                                                                                      b     
     a                                                                        a+b                                                                        b   
     a                              2a+b                                  a+b                                  a+2b                              b            
     a          3a+b            2a+b            3a+2b            a+b            2a+3b            a+2b            a+3b          b            
     a 4a+b 3a+b 5a+2b 2a+b 5a+3b 3a+2b 4a+3b a+b 3a+4b 2a+3b 3a+5b a+2b 2a+5b a+3b a+4b b            
                                                      ..................................................            
                                                      ..................................................
　　
  　　
  
    可以证明，上面的 pa+qb 中 p、q 为互素的自然数，且 同一行中不存在
  
相同的 pa+qb ！ 且 所有 p、q 为互素的自然数的 pa+qb 全部都在其中！
  
  
    金眼睛、lulijie 理解得很透彻，加分支持！ 同时给楼主的主题加精！ 请大家
  
继续探讨研究！
  
  
　　
　　

[ 本帖最后由 ggglgq 于 2009-6-28 21:28 编辑 ]

金眼睛

谢谢G老师了！呵呵。LZ的题好，Cielo提到欧拉函数，就可以想到互质，lulijie给出证明，精华！o(∩_∩)o...

superacid

我一天没来就有人做出来了，看来大家水平很高啊！
贴一下解答。

lulijie

没学过高等数学，不知道欧拉函数是什么，确实孤陋寡闻。
百度了一下，明白了本题的答案就是求N的欧拉函数。
      i+j=2009
   i与j互质，就是i与2009互质，也就是求<=2009的与2009互质的所有正整数的个数，即求2009的欧拉函数。答案就是金眼睛的结果。
学习了。

edmond-xym

是我没有审清题目么？
麻烦问一下根据“如图，先写两个1，然后在每一层的两个数之间插入这两个数的和得下一层”，第三层中间的2是哪里来的？

ursace

这个不是杨辉三角？

ggglgq

原帖由 edmond-xym 于 2009-6-28 23:35 发表
是我没有审清题目么？
麻烦问一下根据“如图，先写两个1，然后在每一层的两个数之间插入这两个数的和得下一层”，第三层中间的2是哪里来的？

　　
  　　

原帖由 ursace 于 2009-6-28 23:38 发表
这个不是杨辉三角？

　　
  　　
  
    这个可不是什么“杨辉三角”  呀！请两位参考：
   
      
     a                                                                                                                                                      b     
     a                                                                        a+b                                                                        b   
     a                              2a+b                                  a+b                                  a+2b                              b            
     a          3a+b            2a+b            3a+2b            a+b            2a+3b            a+2b            a+3b          b            
     a 4a+b 3a+b 5a+2b 2a+b 5a+3b 3a+2b 4a+3b a+b 3a+4b 2a+3b 3a+5b a+2b 2a+5b a+3b a+4b b            
                                                      ..................................................            
                                                      ..................................................
　　
  　　
　　
　　
　　

Cielo

原帖由 lulijie 于 2009-6-28 23:34 发表
没学过高等数学，不知道欧拉函数是什么，确实孤陋寡闻。
百度了一下，明白了本题的答案就是求N的欧拉函数。
……

在不知道的情况下给出证明更是难能可贵啊

大家都很厉害啊！