CUGOJ 1682

한동안 공부한 후에 장 학생은 샤오후가 수학을 매우 잘한다는 것을 발견하고 수학 성적이 좋은 여학생인 샤오후를 추구하기로 결정했다.샤오후는 사실 그를 거절하고 싶었지만 샤오후는 좋은 말을 찾지 못해 이런 요구를 했다. 정해진 두 개의 정수인 N과 M에 대해 장학생은 랜덤으로 N의 인수 Nf를 선택했고 샤오후는 랜덤으로 M의 인수 Mf를 선택했다. 만약에 Nf와 Mf가 같다면 그녀는 장학생에게 승낙했다.
샤오후는 장 학생에게 랜덤 프로그램을 작성하라고 했는데 그때 그녀가 프로그램을 보고 문제가 없으면 추첨을 할 수 있다.그러나 장 학생은 쓰다가 점점 기회가 막연하다고 느꼈다.그렇다면 문제가 생겼다. 장 학생이 샤오후를 따라잡을 확률은 얼마나 될까.
이 문제는 비교적 간단하다. 바로 인자를 구해내는 과정이다.
만약 우리가 n과 m의 인자를 알게 된다면 최종 답은 인자 중 같은 개수를 두 개의 수인자의 곱셈으로 나누는 것이다.그러니까 인자만 구하면 돼.

#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int Gcd(int a, int b)
{
    if (b == 0)return a;
    return Gcd(b, a%b);
}
 
int main()
{
    int t;
    map<long long, int>map_1;
    long long n, m;
    cin >> t;
    while (t--)
    {
        map_1.clear();
        cin >> n >> m;
        if (n == m)
        {
            printf("1 1
");
            continue;
        }
        int p = 0;
        int q = 0;
        for (int i = 1; i <= sqrt(n); i++)
        {
            if (n%i==0)
            {
                if (!map_1[i])map_1[i] = 1,p++;
                if (!map_1[n/i])map_1[n / i] = 1,p++;
            }
        }
        int ans = 0; 
        for (int i = 1; i <= sqrt(m); i++)
        {
            if (m%i==0)
            {
                if (map_1[i])ans++;
                if (i!=m/i&&map_1[m / i])ans++;
                if(i!=m/i)q += 2;
                else q++;
            }
        }
        //cout << ans << " " << p << " " << q << endl;
        int a = Gcd(ans, p * q);
        printf("%d %d
", (p * q) / a, ans / a);
    }
    return 0; 
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Coq에서 증명된 이중 부정 주위의 증명

이중 부정 가져오기 이중 부정 해소를 증명할 수 없지만 삼중 부정 해소를 증명할 수 있다 이중 부정 해소의 이중 부정 이중 부정 해소와 배중률 동치 고전 이론을 얻으려면 직관주의 이론에 어느 것을 넣어도 된다는 것이...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

CUGOJ 1682

좋은 웹페이지 즐겨찾기