Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

多谢指点

Posted by JaneGranger at 2009-09-28 22:25:25 on Problem 1091
In Reply To:解题报告。。。。。。。。。 Posted by:jince at 2009-09-09 20:43:49
> 一份解题报告:
> 跳蚤
> 题目大意是给定两个整数n和m,求出长度为n+1满足条件的数列data的个数,数列的要求下:
> 1)1<=data[i]<=m,for1<=i<=n
> 2)data[n+1]=m;
> 3)这个n+1个数满足:存在x1,x2,...,xn,xn+1,满足x1*data[1]+x2*data[2]+...+x(n+1)*data[n+1]=1;
> 根据数论的知识,若存在这样的x1,x2...xn+1,则data[1],data[2]...data[n+1]的最大公约数为1
> 
> 证明:若data[1],data[2]...data[n+1]满足题意,并且存在最大公约数d(为整数);则x1*data[1]+x2*data[2]+...+x(n+1)*data[n+1]的和是d的整数倍,必不等于1
> 
> 我看到这里的时候还是不明白,这有什么用。。。
> 
> 其实举个例子就明白了,例如:n=2,m=360 
> 360=3^2*2^3*5  所有不满足条件的数列,最大公约数是360质因子的乘积,只要将这些组合去掉,就是要求的答案
> 
> 具体解题步骤如下:
> 1、求出满m的所有质因子,存入数组num
> 2、求出总的序列个数吗m^n
> 3、设t(k)表示数列最大公约数为(k个质因子乘积)的数列的个数
> 
> f=m^n-t(1)+t(2)-t(3)+..(-1)^k*t(k);
> 答案 = (m ^ n) - (有公因数2的n元组)- (有公因数3的n元组)- (有公因数5的n元组)+ (有公因数2,3的n元组) +(有公因数2,5的n元组) + (有公因数3,5的n元组)- (有公因数2,3,5的n元组)。这个比公式形象些
> 有公因数d的n元组,每个位置上有 (m/d)个选择(1 ~ m里面有m/d个d的倍数),根据乘法原理,可以得出有公因数d的n元组有 (m/d)^n 个。
> #include<cstdio>
> #include<cmath>
> #include<iostream>
> 
> using namespace std;
> __int64 n,m,per,total;
> __int64 s[130000],num[130000];
> 
> void totalnum(__int64 x) //求质因子
> {
> 	__int64 i,j;
> 	total=0;
> 	for(i=2;i*i<=x;i++)
> 	{
> 		if(x%i==0)
> 		{
> 			while(x%i==0)
> 				x=x/i;
> 			num[total]=i;
> 			total++;
> 		}
> 	}
> 	if(x!=1)
> 	{
> 		num[total]=x;
> 		total++;
> 	}
> }
> __int64 por(__int64 x,__int64 y)//x^y
> {
> 	__int64 i,k;
> 	k=x;
> 	for(i=1;i<y;i++)
> 		x=k*x;
> 	return x;
> }
> void get(__int64 a,__int64 b,__int64 c)//c:公共质因子个数;
> {
> 	__int64 i;
> 	if(b==c)
> 	{
> 		__int64 t=m;
> 		for(i=0;i<c;i++)
> 		{
> 			t=t/s[i];
> 		}
> 		per+=por(t,n);
> 	}
> 	else
> 	{
> 		for(i=a;i<total;i++)
> 		{
> 			s[b]=num[i];
> 			get(i+1,b+1,c);
> 		}
> 	}
> }
> 
> 
> 
> int main()
> {
> 	__int64 res,i;
> 	while(scanf("%I64d %I64d",&n,&m)!=EOF)
> 	{
> 		totalnum(m);
> 		res=por(m,n);
> 		for(i=0;i<total;i++)
> 		{
> 			per=0;
> 			get(0,0,i+1);
> 			if(i%2==0)
> 			{
> 				res-=per;
> 			}
> 			else
> 			{
> 				res+=per;
> 			}
> 		}
> 		printf("%I64d\n",res);
> 	}
> 	return 0;
> }
(⊙o⊙)哦,我终于明白了

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator