藍橋杯算法提高VIP-排列式

題目

題目連結

題解

全排列。

這種題一般就是全排列，

9! < 4e5

。

這裡有點小技巧，就是結果必然是個四位數，第一個乘數要麼是一位數要麼是兩位數。

為什麼這麼說呢？

我們知道假設第一個乘數

a

位，第二個乘數b``位，那麼他們乘積的位數要麼是

a+b

位，要麼是

a+b-1

位

如果結果是個三位數，那麼還剩六位數，無論将這六位數怎麼配置設定給兩個乘數都無法滿足乘積為三位，同理結果為一位和兩位也都不可能；

如果結果是個五位數，那麼還剩四位，四位數配置設定給兩個乘數最多乘出來個四位數，是以還是不行，同理大于五位更不行；

很顯然隻有結果為四位數可行。當結果為四位數時，乘數可能是多少位呢？

題目要求乘數互換屬于一個式子，同時要求乘數小的先輸出，是以我們隻需考慮第一個乘數的位數，無非是一位或兩位嘛。當第一個乘數為一位時，第二個乘數為四位；當第一個乘數為兩位時，第二個乘數為三位；如果也輸出第一個乘數為三位的情況的話，那麼第二個乘數就是兩位了，這必然會出現重複輸出。是以，我們隻用輸出第一個乘數是一位和兩位的情況就行了。

如何保證使用

next_permutation

就能按要求的大小輸出？

首先我們要明白

next_permutation

的實作原理，正如其名，這個函數就是讓一個元素遞增排序的數組不斷變大，每次後出現的都會大于先出現的。據說它也是通過遞歸實作的，是以不允許排序的個數太多。如果還是不能了解可以完整的輸出一個序列的全部全排列模拟一下。

對于每一種全排列，就對應着一種乘積，我們先輸出第一個是取一位的情況，再輸出第一個乘數為兩位的情況就行了。

代碼

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3;

int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int num1, num2, num3;

int main()
{
	do { 
		// xxxx = x * xxxx
		num1 = num2 = num3 = 0;
		for(int i = 0;i < 4;i ++) num1 = num1*10 + a[i];
		for(int i = 4;i < 5;i ++) num2 = num2*10 + a[i];
		for(int i = 5;i < 9;i ++) num3 = num3*10 + a[i];
		if(num1 == num2*num3) 
		printf("%d = %d x %d\n", num1, num2, num3);
		
		// xxxx = xx * xxx
		num1 = num2 = num3 = 0;
		for(int i = 0;i < 4;i ++) num1 = num1*10 + a[i];
		for(int i = 4;i < 6;i ++) num2 = num2*10 + a[i];
		for(int i = 6;i < 9;i ++) num3 = num3*10 + a[i];
		if(num1 == num2*num3) 
		printf("%d = %d x %d\n", num1, num2, num3);
		
	} while(next_permutation(a, a+9));

	return 0;
}
/*
4396 = 28 x 157
5346 = 18 x 297
5346 = 27 x 198
5796 = 12 x 483
5796 = 42 x 138
6952 = 4 x 1738
7254 = 39 x 186
7632 = 48 x 159
7852 = 4 x 1963
*/