轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 奥数选拔题 [打印本页]

作者: 天宫公主 时间: 2008-2-14 13:49 标题: 奥数选拔题

有多少组 0 至 70 之间的整数 (x, y, z) 使得

13 x^2 y + 4 x^4 z^3 + 5 x^3 y^5 z^6 + 3 y^7 z^16

可以被 71 整除？

P.S. 各位其实也可以编个程序去靠硬算来求解，把每个 (x, y, z) 的组合全试一遍也用不了多少 Machine runtime。

[ 本帖最后由天宫公主于 2008-2-14 13:51 编辑 ]

作者: 菊未央 时间: 2008-2-16 12:57

这是我等闲人该干的事情吗?

作者: 菊未央 时间: 2008-2-16 12:57

更正上贴回复,
这是人该干的事儿吗?

作者: 武骧金星 时间: 2008-2-16 13:08

作为论坛娱乐，能否先给点提示或者解题方向之类的说……

作者: 周瑜 时间: 2008-2-16 13:29

做不出来，我彻底变成计算机的奴隶了。

作者: 炎帝瀑布碎 时间: 2008-2-16 13:31

只会P.S.里的方法

作者: fantasydog 时间: 2008-2-16 13:58

机算了下，412个。
除去x，z都等于0的71个，还有……341个。
奥数有时间的吧……且这个东西要是写在试卷上，能写完么？
————————————————————————————————————
式子列错了…………

貌似有5457组啊。颇夸张了点
---------------------------------------------------------------------------------------------------
天哪，我写程序的能力骤然衰减……居然又错了
---------------------------------------------------------------------------------------------------
小帖一下程序，下班回去再研究：

package fd.misc;

public class Math1 {
      private static final int LIMIT_LOW = 0;

      private static final int LIMIT_HI = 70;

      static int x, y, z;

      /**
      * @param args
      */
      public static void main(String[] args) {
            int count = 0;

            for (x = LIMIT_LOW; x <= LIMIT_HI; x++) {
                     for (y = LIMIT_LOW; y <= LIMIT_HI; y++) {
                              for (z = LIMIT_LOW; z <= LIMIT_HI; z++) {
                                    double result = getResult();

                                    if (result % 71 == 0) {
                                             System.out.println("x=" + x + ",y=" + y + ",z=" + z);
                                             count++;
                                    }
                              }
                     }
            }

            System.out.println(count);
      }

      private static double getResult() {
            return getUnit(13, 2, 1, 0) + getUnit(4, 4, 0, 3) + getUnit(5, 3, 5, 6)
                              + getUnit(3, 0, 7, 16);
      }

      private static double getUnit(int n, int xn, int yn, int zn) {
            return n * Math.pow(x, xn) * Math.pow(y, yn) * Math.pow(z, zn);
      }
}

[ 本帖最后由 fantasydog 于 2008-2-16 14:29 编辑 ]

作者: smalltalk 时间: 2008-2-16 15:35

汗一下楼上的程序，够结构化
问题是，double能用么? java里有没有任意精度整数类型？
话说我的程序跑出来是5083组
顺便赞一下python: "Long integers have unlimited precision"
pow(70, 16) = 332329305696010000000000000000L
pow(2, 64) = 18446744073709551616L

[ 本帖最后由 smalltalk 于 2008-2-16 15:49 编辑 ]

作者: fantasydog 时间: 2008-2-16 16:35

5083是对的。
double太大时，模一个比较小的数就模不出来了。
修改后：
package fd.misc;

public class Math1 {
private static final int LIMIT_LOW = 0;

private static final int LIMIT_HI = 70;

private static final int MAGIC_NUM = 71;

static int x, y, z;

/**
* @param args
*/
public static void main(String[] args) {
int count = 0;

for (x = LIMIT_LOW; x <= LIMIT_HI; x++) {
for (y = LIMIT_LOW; y <= LIMIT_HI; y++) {
for (z = LIMIT_LOW; z <= LIMIT_HI; z++) {
double result = getResult();

if (result % 71 == 0) {
System.out.println("x=" + x + ",y=" + y + ",z=" + z);
count++;
}
}
}
}

System.out.println(count);
}

private static double getResult() {
return getUnit(13, 2, 1, 0) + getUnit(4, 4, 0, 3) + getUnit(5, 3, 5, 6)
+ getUnit(3, 0, 7, 16);
}

private static double getUnit(int n, int xn, int yn, int zn) {
return n * pow(x, xn) * pow(y, yn) * pow(z, zn);
}

private static int pow(int x2, int xn) {
int result = 1;
for(int i=0;i<xn;i++) {
result = result * x2;

result %= MAGIC_NUM;
}
return result;
}
}

PS：对这类问题结构化就够了吧，难道用topcoder的模式写？

[ 本帖最后由 fantasydog 于 2008-2-16 16:40 编辑 ]

作者: 天宫公主 时间: 2008-2-17 17:45

这个。。。5083 肯定有问题的，总数应该不大于 71^2=5041。我也再自己检查一下。。。

作者: 周瑜 时间: 2008-2-18 05:22

main()
{
int x,y,z,i,j;
int sum1,sum2,sum3,sum4,sum,count;
int mod[71][17];
for(i=0;i<71;i++)
for(j=0;j<17;j++)
if(j==0)
mod[i][j]=1;
else
mod[i][j]=mod71(mod[i][j-1]*i);
count=0;
for(x=0;x<71;x++)
for(y=0;y<71;y++)
for(z=0;z<71;z++)
{
sum1=mod71(13*mod[x][2]*mod[y][1]);
sum2=mod71(4*mod[x][4]*mod[z][3]);
sum3=mod71(5*mod[x][3]*mod[y][5]*mod[z][6]);
sum4=mod71(3*mod[y][7]*mod[z][16]);
sum=mod71(sum1+sum2+sum3+sum4);
if(sum==0)
count++;
}
printf("%d\n",count);
}

子程序略，答案是5083。问题是用数学方法怎么做呢。

作者: 天宫公主 时间: 2008-2-18 13:05

如果 5083 是正确答案，说明我的“数学方法”似乎有错误，我再好好检查一下吧。

欢迎光临轩辕春秋文化论坛 (http://www.xycq.org.cn/forum/)