例40 最大公約數問題
題目描述
已知正整數a0、a1、b0、b1，設某未知正整數 x 滿足：
1． x和a0的最大公約數是a1；
2． x和b0的最小公倍數是b1，
現在要求出滿足條件的正整數x，這樣的x 并不唯一，甚至可能不存在，例如，若
a0=41，a1=1，b0=96，b1=288，則x可以是9，18，36，72，144，288，共有6個，
請編程求解滿足條件的 x 的個數，
輸入
第一行為一個正整數 n，表示有 n 組輸入資料，接下來的n 行，每行一組輸入資料，為四個正整數a0，a1，b0，b1，每兩個整數之間用一個空格隔開，輸入資料保證 a0能被 a1整除，b1能被 b0整除，
輸出
共 n 行，每組輸入資料的輸出結果占一行，為一個整數，
對于每組資料：若不存在這樣的 x，請輸出 0，若存在這樣的 x，請輸出滿足條件的 x 的個數，
輸入樣例
2
41 1 96 288
95 1 37 1776
輸出樣例
6
2
（1）編程思路，
顯然，若x存在，x一定是b1的因子，因此，可以對b1的因子（1~sqrt(b1)）進行窮舉，對每個x，判斷其是否滿足兩個條件，若滿足，則計數；同時若另一個因子b1/x也滿足條件，同樣計數，
（2）源程式，
#include <stdio.h>
int gcd(int a,int b)
{
int r=a%b;
while (r!=0)
{
a=b; b=r; r=a%b;
}
return b;
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int a0,a1,b0,b1;
scanf("%d%d%d%d",&a0,&a1,&b0,&b1);
int ans=0;
int x;
for (x=1;x*x<=b1;x++) // 窮舉b1的因子
{
if (b1%x==0)
{
if (x%a1==0 && gcd(x,a0)==a1 && x/gcd(x,b0)*b0==b1) ans++;
int y=b1/x; // b1的另一個因子
if (x==y) continue;
if (y%a1==0 && gcd(y,a0)==a1 && y/gcd(y,b0)*b0==b1) ans++;
}
}
printf("%d\n",ans);
}
return 0;
}
習題40
40-1 回圈的數字
本題選自洛谷題庫 （https://www.luogu.org/problem/P1611）
題目描述
兩個不同的正整數（n，m）是回圈的，當且僅當能通過將n末端的幾個數字移到它的首端而不改變移動的數字的順序并使整個數字變成m，舉個例子， (12345，34512) 就是一對回圈的數字，因為能把12345中末尾的345移到12前面，從而得到34512，注意，為了成為一對回圈的數字，n和m位數必須相同，無論n 或m都沒有前置的0，
現在給定正整數A和B（1≤A,B≤2×106），并保證A和B位數相同且均沒有前置0，求存在多少回圈的正整數對 (n,m)，使得A≤n≤m≤B ？
輸入
輸入包含1 行，有兩個用空格隔開的正整數 A和B，
輸出
輸出一個正整數x，表示共有x 組回圈的正整數對(n,m)，使得A≤n≤m≤B，
輸入樣例
1111 2222
輸出樣例
287
（1）編程思路，
對n進行窮舉，范圍為a≤n≤b，
一個整數n，設其位數為k，可以用運算式(n%10)*10k-1+n/10求出其一個回圈數，
例如，設n=12345，則(12345%10)*10000+(12345/10)=51234；
(51234%10)*10000+(51234/10)=45123，…，
（2）源程式，
#include <stdio.h>
int main()
{
int a,b;
scanf("%d%d",&a,&b);
int p[7]={1,10,100,1000,10000,100000,1000000};
int ans=0;
int len=0, t=a;
while (t!=0)
{
len++;
t/=10;
}
int n,m;
for (n=a;n<=b;n++) // 列舉n
{
m=(n%10)*p[len-1]+n/10;
while (n!=m) // 若n==m，則m列舉完畢
{
if (n<m && m<=b)
ans++;
m=(m%10)*p[len-1]+m/10;
}
}
printf("%d\n",ans);
return 0;
}
40-2 5個砝碼
問題描述
用天平稱重時，我們希望用盡可能少的砝碼組合稱出盡可能多的重量，
如果只有5個砝碼，重量分別是1，3，9，27，81，則它們可以組合稱出1到121之間任意整數重量（砝碼允許放在左右兩個盤中），
本題目要求編程實作：對用戶給定的重量，給出砝碼組合方案，
輸入
輸入包含多組測驗用例，每個測驗用例為1行，一個整數n，其范圍為1~121，表示用戶要稱的重量，
輸出
對給定的重量，輸出砝碼組合方案，要求輸出的組合總是大數在前小數在后，
輸入樣例
5
19
輸出樣例
9-3-1
27-9+1
（1）編程思路1，
砝碼只有5個，且每次稱重時，這5個砝碼中的每一個只能出現0次或者1次，且砝碼要么在物體盤，要么在砝碼盤，故可做如下約定：
若砝碼放在物體盤，約定其出現-1次；
若砝碼放在砝碼盤，約定其出現1次；
若稱重時不需要該砝碼，約定其出現0次，
設5個砝碼在每次稱重中出現的次數分別為x1、x2、x3、x4、x5，則這5個數每個只有-1、0、1這三種取值，對這243種情況進行窮舉，看其組合是否符合稱重要求即可，
（2）源程式1，
#include <stdio.h>
int main()
{
int v[6]={0,81,27,9,3,1};
int n;
while (scanf("%d",&n)!=EOF)
{
int x[6],flag;
flag=0;
for (x[1]=-1;x[1]<=1 && !flag; x[1]++)
for (x[2]=-1;x[2]<=1 && !flag; x[2]++)
for (x[3]=-1;x[3]<=1 && !flag; x[3]++)
for (x[4]=-1;x[4]<=1 && !flag; x[4]++)
for (x[5]=-1;x[5]<=1 && !flag;x[5]++)
if (81*x[1]+27*x[2]+9*x[3]+3*x[4]+x[5]==n)
{
int i;
for (i=1;i<=5;i++)
{
if (x[i]>0)
{
if (flag==0) printf("%d",v[i]);
else printf("+%d",v[i]);
flag=1;
}
else if (x[i]<0) printf("-%d",v[i]);
}
printf("\n");
}
}
return 0;
}
（3）編程思路2，
實際上本題不用窮舉可以直接計算出來，
1、3、9、27、81正好是一個三進制五位數各位上的權值，1+3+9+27+81=121，最大能夠稱出121的物體來，但是要稱重n，如何組合呢？
由于可以把砝碼加在天平的物體盤中，因此，放在物體盤中的砝碼不是要加在稱出的重量上面，而是要從中減去的數，例如，5=9-3-1、6=9-3、7=9+1-3等等，
為了達到這個目的，設所用的三進制數碼不是通常的0、1、2，而是-1、0、1，即2可以寫成3-1，將其轉化成-1這個數字，為了簡便，把-1寫成i，以后只要在三進制中碰到2這個數字，就把它改寫成1i（即3-1=2），例如，三進制中的2102這個數，可以用下面的方法改寫成1i11i，
2102 = 2000 + 100 + 2 = 1i000 +100 + 1i = 1i000 +11i = 1i11i
來看幾個實際重量的稱重情況，
例如，為了稱出14克，先將14化成普通三進制112，再進行改寫，112=100+10+1i=100+2i=100+20+i = 100 +1i0 +i =100 +1ii = 2ii =1iii，這就是說，把27這塊砝碼放進砝碼盤，而把9、3、1三塊砝碼放進稱物盤中，就可以稱出14克出來（27-9-3-1=14），
再看怎樣稱出26克來，26化成普通三進制222，進行改寫，222=1i00+1i0+1i=1i00+10i=100i，這就是說，把27這塊砝碼放進砝碼盤，而把1這塊砝碼放進物體盤中，就可以稱出26克出來（27-1=26），
由此，可以看出用五塊砝碼能稱出121以下所有整數重量的物體，
（4）源程式2，
#include <stdio.h>
int main()
{
int v[6]={1,3,9,27,81};
int n;
while (scanf("%d",&n)!=EOF)
{
int x[6]={0},i,k=0;
while (n!=0)
{
x[k++]=n%3;
n=n/3;
}
for (i=0;i<k;i++)
{
if (x[i]==3)
{
x[i]=0; x[i+1]++;
}
else if (x[i]==2)
{
x[i]=-1; x[i+1]++;
}
}
if (x[k]!=0) k++;
printf("%d",v[k-1]);
for (i=k-2;i>=0;i--)
{
if (x[i]>0) printf("+%d",v[i]);
else if (x[i]<0) printf("-%d",v[i]);
}
printf("\n");
}
return 0;
}
40-3 聊天音量
問題描述
約翰的農場上有N頭奶牛（1≤N≤105），第i 頭奶牛的位置為 xi（0≤xi≤109 ），
奶牛很健談，每頭奶牛都和其他N?1 頭奶牛聊天，第i頭奶牛和第j頭奶牛聊天時，音量為 |xi-xj|，
請您求出所有奶牛聊天音量的總和，
輸入
第一行一個整數N，
接下來N 行，每行一個整數 xi，
輸出
輸出總音量，保證答案在 64 位帶符號整數的表示范圍內，
輸入樣例
5
1
5
3
2
4
輸出樣例
40
（1）編程思路1，
直接列舉計算每頭牛與其他位置的牛的聊天音量和，
（2）源程式1，
#include <stdio.h>
int main()
{
int n;
scanf("%d",&n);
long long x[100001];
int i,j;
for (i=1;i<=n;i++)
scanf("%lld",&x[i]);
long long ans=0;
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
{
ans+=x[i]>x[j]?x[i]-x[j]:x[j]-x[i];
}
printf("%lld\n",ans * 2);
return 0;
}
這個程式提交后，測驗點Subtask #0（N≤104）可以過，但測驗點Subtask #1全部超時，
（3）編程思路2，
為了減少計算量，將x升序排列，
定義陣列s[100001]，其中s[i]表示位置i的牛和位置比其小的所有牛的聊天的音量的和，則有
S[1]=0
S[2]=x[2]-x[1]
S[3]=x[3]-x[1]+x[3]-x[2]=2*(x[3]-x[2])+(x[2]-x[1]) =2*(x[3]-x[2])+s[2]
S[4]=x[4]-x[1]+x[4]-x[2]+x[4]-x[3]=3*(x[4]-x[3])+(x[3]-x[2])+(x[3]-x[1]) =3*(x[4]-x[3])+s[3]
?……
由此得到遞推式： S[i]=(i-1)*(x[i]-x[i-1])+s[i-1]
（4）源程式2，
#include <stdio.h>
#include <algorithm>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
long long x[100001],s[100001]={0};
int i,j;
for (i=1;i<=n;i++)
scanf("%lld",&x[i]);
sort(x+1,x+n+1);
long long ans=0;
for (i=2;i<=n;i++)
{
s[i]=(i-1)*(x[i]-x[i-1])+ s[i-1];
ans+=s[i];
}
printf("%lld\n",ans * 2);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/400308.html
標籤：其他
上一篇：再見，CentOS！2021/12/31 宣布正式停服。。
下一篇：01 Java基礎