jzoj 3509. 【NOIP2013模拟11.5B组】倒霉的小C(math)

3509. 【NOIP2013模拟11.5B组】倒霉的小C

(File IO): input:beats.in output:beats.out
Time Limits: 1000 ms Memory Limits: 262144 KB Detailed Limits
Goto ProblemSet

Description

小G最近迷上了岛国动漫《Angel Beats》，她为了画出一个更霸气的Angel Beats的logo，想了如下办法：

从（0，0）开始，画到（n，1），再从（n，1），画到（2*n，-1），再到（3*n，2），再到（4*n，-2），依此类推，即每次画出一个（n，(-1)^(i+1)*i）的向量，一共画出n个这样的向量。现在小G想让小C求出这个图形穿过了多少格点（坐标都是整数）。

由于小C想要认真地听他的数学课并且想自己在接力赛中因RP暴光而发生接力棒传错这类的糗事，所以这个问题就交给你啦。小G说，如果连你也解决不好，就把你的RP也吸光。

Input

输入文件中仅一行为一个整数n。

Output

输出文件中仅一行为一个数，表示穿过的格点数。

Sample Input

4

Sample Output

9

Data Constraint

对于20%的数据，满足：n<=100；

对于40%的数据，满足：n<=10^5；

对于60%的数据，满足：n<=10^7；

对于100%的数据，满足：n<=10^10。

分析：通过简单观察可以发现，每次画出向量（n，i）经过的格点个数为gcd(i，n)，那么答案就等于Ans=1+Σgcd（i,n）
直接求解的时间复杂度是O(n)的。
那么Ans=1+Σd*phi(n/d)，其中d为n的约数。fai(n)表示1～n中与n互质的数的个数。通过这样的变形，我们就可以得到时间复杂度为O(C*sqrt(n))的算法，C为n的约数个数。

代码

#include 
#include 
#include 
#define N 20000
#define ll long long
using namespace std;ll n;ll phi(ll x)
{ll s=x;for (ll i=2;x>1;i++)if (x%i==0){s-=s/i;while (x%i==0) x/=i;}return s;
}int main()
{freopen("beats.in","r",stdin);freopen("beats.out","w",stdout);scanf("%lld",&n);ll ans=0;ll m=sqrt(n);for (ll i=1;i<=m;i++)if (n%i==0) {ans+=i*phi(n/i);ll k=n/i;if ((n/i)!=(n/k)) ans+=k*phi(n/k);}printf("%lld",ans+1);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！