3509. 【NOIP2013模拟11.5B組】倒黴的小C(beats)
(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 做法：
通過簡單觀察可以發現，每次畫出向量（n，i）經過的格點個數為gcd(i，n)，那麼答案就等于Ans=1+
直接求解的時間複雜度是O(n)的。
那麼Ans=1+
其中d為n的約數。fai(n)表示1～n中與n互質的數的個數。通過這樣的變形，我們就可以得到時間複雜度為O(C*sqrt(n))的算法，C為n的約數個數。
代碼如下：
1 #include <cstdio>
2 #include <iostream>
3 #include <string>
4 #include <cstring>
5 #include <cmath>
6 #define LL long long
7 using namespace std;
8 LL n, ans, k;
9
10 LL phi(LL x)
11 {
12 LL k = x;
13 for (int i = 2; x > 1; i++)
14 if (x % i == 0)
15 {
16 k -= k / i;
17 while (x % i == 0) x /= i;
18 }
19 return k;
20 }
21
22 int main()
23 {
24 freopen("beats.in", "r", stdin);
25 freopen("beats.out", "w", stdout);
26 cin >> n;
27 int p = sqrt(n);
28 for (int i = 1; i <= p; i++)
29 if (n % i == 0)
30 {
31 k = i;
32 ans += k * phi(n / k);
33 if (k != n / k) k = n / i, ans += k * phi(n / k);
34 }
35 cout << ans + 1;
36 return 0;
37 } View Code
轉載于:https://www.cnblogs.com/traveller-ly/p/9338603.html