Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

贴个40行的DFS，这题真的挺扯的。。不过可能是数据比较弱

Posted by s13a_qw4990 at 2013-05-16 21:23:46 on Problem 2132
```#include<iostream>
#include<cstring>
#include<map>
using namespace std;

#define ll long long

int n,C[30][30];
map <ll,bool> vis[30];
ll ANS;
bool flag[30];

ll gcd(ll a,ll b){
if(!b)  return a;
return gcd(b,a%b);
}
void dfs(int u,int val){
if(vis[u][val] == 1)    return ;
vis[u][val] = 1;
if(u == 2){
ANS /= gcd(ANS,val);
ANS *= val;
return ;
}
flag[u] = 1;
for(int v=1;v<=n;v++)   if(C[u][v] && !flag[v])
dfs(v,gcd(C[u][v],val));
flag[u] = 0;
}

int main(){
while(cin >> n){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin >> C[i][j];
for(int i=1;i<=n;i++)   vis[i].clear();
ANS = 1;
memset(flag,0,sizeof(flag));
dfs(1,0);
cout << ANS << endl;
}
return 0;
}
```

Followed by: