C. 最大公约数 II http://icpc.upc.edu.cn/problem.php?cid=1630&pid=2
分解因子 + 欧拉函数
- #include <iostream>
- #include<cstdio>
- #include<cmath>
- #include<cstring>
- #include<algorithm>
- typedef long long ll;
- using namespace std;
- ll ans1,asn2;
- ll get_phi(ll x){
- ll ret=x;
- for(ll i=2;i*i<=x;i++)
- if(x%i==0){
- ret/=i,ret*=(i-1);
- while(x%i==0)x/=i;
- }
- if(x>1)ret/=x,ret*=x-1;
- return ret;
- }
- int main()
- {
- ll n;scanf("%lld",&n);
- ll i;
- ll ans1,ans2;
- for(i=1;i*i<=n;i++){
- if(n%i==0){
- ans1=i;
- ans2=get_phi(n/i);
- printf("%lld %lld\n",ans1,ans2);
- }
- }
- if(sqrt(n)*sqrt(n)==n) i-=2;
- else i-=1;
- for(i;i>=1;i--){
- if(n%i==0){
- ans1=n/i;
- ans2=get_phi(i);
- printf("%lld %lld\n",ans1,ans2);
- }
- }
- return 0;
- }
- View Code
A. 花 http://icpc.upc.edu.cn/problem.php?cid=1630&pid=0
dp
来源: http://www.bubuko.com/infodetail-2923590.html