HDU 1695 GCD 오로라 함수 + 용 반 정리
1732 단어 HDU
gcd (x, y) = k 는 b 와 d 를 모두 k 문제 로 나 누 어 1 에서 b / k, 1 에서 d / k 2 구간 으로 바 꾸 기 때문에 첫 번 째 구간 이 두 번 째 구간 보다 작 으 면 두 번 째 구간 을 2 부분 으로 나 누 어 1 - b / k 와 b / k + 1 - d / k 를 한다.
첫 번 째 부분 에서 모든 수 i 와 그의 상호 질 에 대한 수 는 바로 이 수의 오 라 함 수치 전체 수의 오 라 함수 의 합 이 바로 답 이다.
두 번 째 부분 은 모든 수로 서로 질 이 없 는 수 를 줄 일 수 있다.
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int maxn = 100010;
LL phi[maxn];
LL sum[maxn], p[maxn][33];
void phi_table(int n)
{
memset(sum, 0, sizeof(sum));
memset(phi, 0, sizeof(phi));
phi[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!phi[i])
for(int j = i; j <= n; j += i)
{
if(!phi[j])
phi[j] = j;
phi[j] = phi[j] / i * (i-1);
p[j][sum[j]++] = i;
}
phi[i] += phi[i-1];
}
}
void dfs(int id, LL num, LL cnt, int a, LL& ans, int x)
{
if(id == sum[x])
{
if(cnt == 0)
return;
if(cnt&1)
ans += a/num;
else
ans -= a/num;
return;
}
dfs(id+1, num*p[x][id], cnt+1, a, ans, x);
dfs(id+1, num, cnt, a, ans, x);
}
LL cal(int x, int a)
{
LL ans = 0;
dfs(0, 1, 0, a, ans, x);
return ans;
}
int main()
{
phi_table(100000);
int cas = 1;
int T;
scanf("%d", &T);
while(T--)
{
int a, b, k;
scanf("%d %d %d %d %d", &a, &a, &b, &b, &k);
if(!k)
{
printf("Case %d: %d
", cas++, 0);
continue;
}
if(a > b)
swap(a, b);
a /= k;
b /= k;
LL ans = phi[a];
for(int i = a+1; i <= b; i++)
ans += a-cal(i, a);
printf("Case %d: %I64d
", cas++, ans);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[HDU] 4089 활성화 확률 DPdp[i][j]를 모두 i개인의 대기열인 Tomato가 j위 서버가 마비될 확률로 역추를 사용하면 우리는 상태 이동 방정식을 얻을 수 있다. i == 1 : dp[1][1] = dp[1][1] * p1 + dp[1]...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
