Codecrafr-20(Div.2) C. Primitive Primes

풀려고 생각하다가 끝난 문제였다

한시간이 넘도록 생각해도 못풀었다 ㅎㅎ 수학적 머리가 없는건가

 

우선 f,g 계수들의 gcd가 1이기 때문에 어딘가 p로 안나눠떨어지는 수가 하나씩은 나온다!

 

f에서 그위치를 i / g에서는 j라고 해보자

 

f*g=h일때 h의 계수를 생각해보면

h^(i+j)의 계수는 f와g의 index합이 i+j인것들의 합이다

 

이 때 fi*gj도 포함되는데 이 수는 각각 p로 안나눠지므로 두 수의곱도 당연히 안나눠진다!

그래서 답은 그냥 안나눠지는 위치 두개를 찾아서 더하면 된다

 

수학적으로 증명해서 알려주면 참 쉬워보이는데 시간안에 어케해야할까 이걸..!!

수학은 어렵다..!

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int n,m,a,b,p;
int main(){
    scanf(" %d %d %d",&n,&m,&p);
    for(int i=0;i<n;i++){
        int x; scanf(" %d",&x);
        if(x%p) a=i; 
    }
    for(int i=0;i<m;i++){
        int x; scanf(" %d",&x);
        if(x%p) b=i; 
    }
    printf("%d\n",a+b);
}