Problem F 6 方格填数
问题描述
万神在纸上画了一个 3 × 3 的表格,希望把 1 · · · 9 填入表格中,每个数只填
一次。然而,这样会有 9! = 362880 种不同的填数方案。万神觉得方案太多了,
于是又写下 9 个正整数 a 1 · · · a 9 ,并规定填数方案合法的充要条件是:对于表格
中任意一对相邻的数 x, y,必须满足 a x 和 a y 互质,即它们的最大公约数是 1。
那么,还有多少种合法的填数方案呢?
相邻定义为两个数所在的格子有公共边。
输入格式
输入包含多组数据(最多 100 组),请处理到文件结束。
每组数据只有 1 行,包含 9 个正整数 a 1 · · · a 9 ,用空格分割。
保证 1 ≤ a i ≤ 10 9 。
输出格式
对于每组数据输出 1 行,包含 1 个整数,即合法的填数方案的个数。
输入样例
1 1 1 1 1 1 1 1 1
2 2 2 4 4 4 6 6 6
2 2 2 2 2 3 3 3 3
输出样例
362880
0
2880
样例解释
对于第一组样例,所有方案都是合法的。
对于第二组样例,所有方案都是不合法的。
对于第三组样例,必须把 1 · · · 5 放在表格的两条对角线上,6 · · · 9 放在其他
4 个格子上,所以有 5! × 4! = 2880 种方案。
思路：
深搜么！！～～～～
/*************************************************************************
> File Name: f.cpp
> Author: dulun
> Mail: dulun@xiyoulinux.org
> Created Time: 2016年04月20日 星期三 14时45分24秒
************************************************************************/
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 50086;
int ans = 0;
bool over = 0;
int a[10];
int now[10];
bool v[10];
int gcd(int a, int b)
{
return a%b==0 ? b : gcd(b, a%b);
}
bool check(int cur, int k)
{
if(cur == 0)
return true;
if(cur - 3 >= 0)
{
if(gcd(now[cur-3], k) != 1) return false;
}
if(cur % 3 != 0 )
{
if(gcd(now[cur-1], k) != 1) return false;
}
return true;
}
void dfs(int cur)
{
if(cur == 9)
{
ans++;
return;
}
for(int i = 0; i < 9; i++)
{
if(v[i] == true) continue;
if(check(cur, a[i]) == true)
{
v[i] = 1;
now[cur] = a[i];
dfs(cur+1);
v[i] = 0;
}
}
}
int main()
{
while(~scanf("%d", &a[0]))
{
ans = 0;
for(int i = 1; i < 9; i++)
{
scanf("%d", &a[i]);
}
dfs(0);
if(over == 1)
{
printf("0\n");
continue;
}
printf("%d\n", ans);
}
return 0;
}