Codeforces Round #779 (Div. 2) Problem B. Marin and Anti-coprime Permutation

문제를 이해한 후 input/ output을 보면 먼저 짝수일 경우에만 답이 존재한 다는 것을 알 수 있다.

또한 gcd 이므로 일정한 규칙에 영향을 받아 갯수가 정해질텐데.... 라는 생각으로 정답을 소인수 분해 해보면 규칙을 찾을 수 있다.

input이 2 일 경우 정답 : 1^2

input이 4 일 경우 정답 : 1^2 * 2^2

input이 6일경우 정답 : 1^2 * 2^2 * 3^2

 

라는 규칙을 찾을 수 있다.

이후 큰 값에 의해 모듈러 연산을 수행해야 하는데, 이 경우 아래 코드처럼 해야 한다.

 

<소스코드>

#include<iostream>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<cmath>
 
//#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int T;
    cin>>T;
 
    for(int t = 0; t<T; t++){
        
        ll n;
        cin>>n;
        if(n%2 != 0){
            cout<<0<<endl;
        }
        else{
            ll g = n/2;
            ll ans = 1;
            for(ll i = 1; i<=g; i++)
                ans = (ans * ((i*i)%998244353))%998244353;
            
            cout<<ans<<endl;
        }
       
    }
}

<문제>

https://codeforces.com/contest/1658/problem/B

Problem - B - Codeforces