倒霉的小C【数论】

题目大意：

小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也吸光。

思路：

50分做法：

直接求上式，时间复杂度O(nlogn)

100分做法： 
随便取一个数，找一下规律。

• 12

分解后为

• 1 2 3 4 1 6 1 4 3 2 1 12

再统计一下每个数字的个数。

• 1：4
• 2：2
• 3：2
• 4：2
• 6：1
• 12：1

不难发现，数字ii出现的次数就是φni
那么就枚举nn的约数，求出φi和φni，计算答案即可。 
时间复杂度：约O(√n)

代码：

#include 
#include 
#include 
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
using namespace std;long long ans,sum,n,a;long long phi(long long x)  //求phi[i]
{ans=x;for (long long i=2;i*i<=x;i++)if (!(x%i)){ans=ans/i*(i-1);while (!(x%i)) x/=i;}if (x>1) ans=ans/x*(x-1);return ans;
}int main()
{fre(beats);scanf("%lld",&n);for (long long i=1;i*i<=n;i++)  //枚举约数if (!(n%i)) {sum+=i*phi(n/i);if (i*i!=n) sum+=(n/i)*phi(i);  //不是完全平方数
     }printf("%lld\n",sum+1);return 0;
}

转载于:https://www.cnblogs.com/hello-tomorrow/p/9332352.html

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