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 zwt395081716 at 2011-02-25 12:28:10 on Problem 1091
题目给出了n和m,要求出满足最大公约数(x1,x2,...,xn,m)=1且xi不超过m的这样的x1,...,xn的组数。xi都是正整数。

如果n=1,那就是求欧拉函数。我们可以联想其形式:。那么当n>1时我们也来类比一下相对应的公式。

令表示题目中所要求的答案。我们发现,当m为素数时,。这是显然的,因为除了(m,m,...,m,m)这一组数字以外,其余的都是可行的解。那么m不为素数时,我们把m的各个素因数分开考虑。如果某个素因数被n个数所共有,那么一共就少了种方案,考察m所有的素因数,我们得到。

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