題目大意是給定兩個整數(shù)n和m，求出長度為n+1滿足條件的數(shù)列data的個數(shù)，數(shù)列的要求下：
1）1<=data[i]<=m,for1<=i<=n
2)data[n+1]=m;
3）這個n+1個數(shù)滿足：存在x1,x2,...,xn,xn+1,滿足x1*data[1]+x2*data[2]+...+x(n+1)*data[n+1]=1；
根據(jù)數(shù)論的知識，若存在這樣的x1,x2...xn+1,則data[1],data[2]...data[n+1]的最大公約數(shù)為1

證明：若data[1],data[2]...data[n+1]滿足題意，并且存在最大公約數(shù)d（為整數(shù)）;則x1*data[1]+x2*data[2]+...+x(n+1)*data[n+1]的和是d的整數(shù)倍，必不等于1

其實舉個例子就明白了，例如:n=2,m=360
360=3^2*2^3*5? 所有不滿足條件的數(shù)列，最大公約數(shù)是360質(zhì)因子的乘積，只要將這些組合去掉，就是要求的答案

具體解題步驟如下：
1、求出滿m的所有質(zhì)因子,存入數(shù)組num
2、求出總的序列個數(shù)嗎m^n
3、設(shè)t(k)表示數(shù)列最大公約數(shù)為（k個質(zhì)因子乘積）的數(shù)列的個數(shù)

f=m^n-t(1)+t(2)-t(3)+..(-1)^k*t(k);
答案 = (m ^ n) - （有公因數(shù)2的n元組）- （有公因數(shù)3的n元組）- （有公因數(shù)5的n元組）+ （有公因數(shù)2，3的n元組） +（有公因數(shù)2，5的n元組） + （有公因數(shù)3，5的n元組）- （有公因數(shù)2，3，5的n元組）。這個比公式形象些
有公因數(shù)d的n元組，每個位置上有 (m/d)個選擇（1 ~ m里面有m/d個d的倍數(shù)），根據(jù)乘法原理，可以得出有公因數(shù)d的n元組有 (m/d)^n 個。 View Code ?1?#include<iostream>
?2?#include<cstdio>
?3?#include<cmath>
?4?using?namespace?std;
?5?__int64?n,m,per,total;
?6?__int64?s[130000],num[130000];
?7?
?8?void?totalnum(__int64?x)//求質(zhì)因子
?9?{
10?????__int64?i;
11?????total=0;
12?????for(i=2;i*i<=x;i++)
13?????{
14?????????if(x%i==0)
15?????????{
16?????????????while(x%i==0)?x=x/i;
17?????????????num[total++]=i;
18?????????}
19?????}
20?????if(x!=1)?num[total++]=x;
21?}
22?
23?__int64?por(__int64?x,__int64?y)//總的序列個數(shù)
24?{
25?????__int64?i,k;
26?????k=x;
27?????for(i=1;i<y;i++)
28?????????x=k*x;
29?????return?x;
30?}
31?
32?void?get(__int64?a,__int64?b,__int64?c)
33?{//a:序列起始位置?b個質(zhì)因子乘積，c:公共質(zhì)因子個數(shù)
34?????__int64?i;
35?????if(b==c)
36?????{
37?????????__int64?t=m;
38?????????for(i=0;i<c;i++)
39?????????????t=t/s[i];
40?????????per+=por(t,n);
41?????}
42?????else?
43?????{
44?????????for(i=a;i<total;i++)
45?????????{
46?????????????s[b]=num[i];
47?????????????get(i+1,b+1,c);
48?????????}
49?????}
50?}
51?
52?int?main()
53?{
54?????__int64?sum,i;
55?????while(scanf("%I64d%I64d",&n,&m)!=EOF)
56?????{
57?????????totalnum(m);
58?????????sum=por(m,n);
59?????????for(i=1;i<=total;i++)
60?????????{
61?????????????per=0;
62?????????????get(0,0,i);
63?????????????if(i%2==1)
64?????????????????sum-=per;
65?????????????else?sum+=per;
66?????????}
67?????????printf("%I64d\n",sum);
68?????}
69?????return?0;
70?}

轉(zhuǎn)載于:https://www.cnblogs.com/yueshuqiao/archive/2012/02/29/2372783.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1091（数论）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。