板子题（卡常）
也可能是用map太慢了/************************************************************** Problem: 3944 User: walfy Language: C++ Result: Accepted Time:9932 ms Memory:84304 kb****************************************************************/ //#pragma GCC optimize(2)//#pragma GCC optimize(3)//#pragma GCC optimize(4)//#pragma GCC optimize("unroll-loops")//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include #define fi first#define se second#define db double#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define vi vector #define mod 1000000007#define ld long double#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pll pair #define pil pair #define pli pair #define pii pair //#define cd complex #define ull unsigned long long#define base 1000000000000000000#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))#define fin freopen("a.txt","r",stdin)#define fout freopen("a.txt","w",stdout)#define fio ios::sync_with_stdio(false);cin.tie(0)template inline T const& MAX(T const &a,T const &b){return a>b?a:b;}template inline T const& MIN(T const &a,T const &b){return a =mod)a-=mod;}inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;} using namespace std; const double eps=1e-8;const ll INF=0x3f3f3f3f3f3f3f3f;const int N=5000000+10,maxn=400000+10,inf=0x3f3f3f3f; int prime[N],cnt,mu[N];ll phi[N];bool mark[N];map muu;map ::iterator it1;map phii;map ::iterator it2;void init(){ mu[1]=phi[1]=1; for(int i=2;i se; ll ans=1; for(ll i=2,j;i<=n;i=j+1) { j=n/(n/i); ans-=1ll*(j-i+1)*getmu(n/i); } return muu[n]=ans;}ll getphi(ll n){ if(n se; ll ans=n*(n+1)/2; for(ll i=2,j;i<=n;i=j+1) { j=n/(n/i); ans-=1ll*(j-i+1)*getphi(n/i); } return phii[n]=ans;}int main(){ init(); int T;scanf("%d",&T); while(T--) { ll n;scanf("%lld",&n); printf("%lld %lld\n",getphi(n),getmu(n)); } return 0;}/********************102147483638214748363921474836402147483641214748364221474836432147483644214748364521474836462147483647********************/ 不用map的版本
/************************************************************** Problem: 3944 User: walfy Language: C++ Result: Accepted Time:7600 ms Memory:67700 kb****************************************************************/ //#pragma GCC optimize(2)//#pragma GCC optimize(3)//#pragma GCC optimize(4)//#pragma GCC optimize("unroll-loops")//#pragma comment(linker, "/stack:200000000")//#pragma GCC optimize("Ofast,no-stack-protector")//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include #define fi first#define se second#define db double#define mp make_pair#define pb push_back#define pi acos(-1.0)#define ll long long#define vi vector #define mod 1000000007#define ld long double#define C 0.5772156649#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#define pll pair #define pil pair #define pli pair #define pii pair //#define cd complex #define ull unsigned long long#define base 1000000000000000000#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)<(b)?(a):(b))#define fin freopen("a.txt","r",stdin)#define fout freopen("a.txt","w",stdout)#define fio ios::sync_with_stdio(false);cin.tie(0)template inline T const& MAX(T const &a,T const &b){return a>b?a:b;}template inline T const& MIN(T const &a,T const &b){return a =mod)a-=mod;}inline void sub(ll &a,ll b){a-=b;if(a<0)a+=mod;}inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}inline ll qp(ll a,ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;a=a*a%mod,b>>=1;}return ans;}inline ll qp(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=ans*a%c;a=a*a%c,b>>=1;}return ans;} using namespace std; const double eps=1e-8;const ll INF=0x3f3f3f3f3f3f3f3f;const int N=2000000+10,maxn=400000+10,inf=0x3f3f3f3f; int prime[N],cnt,mu[N];ll phi[N],n,muu[N],phii[N];bool mark[N],vis[N];void init(){ mu[1]=phi[1]=1; for(int i=2;i