當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

以行走般的速度β

發(fā)布時間：2024/10/5 编程问答 26 豆豆

生活随笔收集整理的這篇文章主要介紹了以行走般的速度β 小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1008&cid=832

https://codeforces.com/contest/1062/problem/D

Problem Description

In the world line 1.048596%

今天的理科實驗室依舊回響著氣泡的大合唱。

梓川咲太一邊看應(yīng)考的題目一邊聽著聲音的變化，同時思索該如何回答考察數(shù)學思維的題目......

就算解決了牧之原翔子和櫻島麻衣的問題，也終究要面對現(xiàn)實的考驗。

“梓川你不是要和櫻島麻衣前輩考同一個大學嗎？”

雙葉理央坐在咲太的面前，今天也依然披著白大褂，正在準備不知名的實驗。

“是啊。之前不是說過嗎？所以我現(xiàn)在忙于備考。”

“我就友善的提醒你一句...”

“什么？”

“你看的是我的算法競賽書......”雙葉理央用略帶擔憂的聲音這么說著。

梓川咲太突然回過神來，他翻了翻書本后面的內(nèi)容，的確是和程序有關(guān)。但是前面的例題部分做的卻和普通的參考書別無二致。

雙葉拿回了她的算法書，找著梓川剛剛在看的部分。

“給出一個大于等于2的正整數(shù)n，對于一對數(shù)a和b(2<=|a|,|b|<=n,a!=b)，如果存在一個整數(shù)x(|x|>=1)使得ax=b（或bx=a)，就可以將a轉(zhuǎn)換成b（或?qū)轉(zhuǎn)換為a），轉(zhuǎn)換后，你可以獲得|x|的積分。”

一邊說著，雙葉就開始在黑板上寫一些算式。

“不過，限制條件是，轉(zhuǎn)換完畢后，就不能再使用由a轉(zhuǎn)換成b或b轉(zhuǎn)換成a的轉(zhuǎn)換方式了。“

”一開始擁有的積分是0，現(xiàn)在給一個大于等于2的正數(shù)n，可以在2~n都取一次起點進行轉(zhuǎn)換（更換起點時，轉(zhuǎn)換方式不初始化）。請問最多可以獲得多少分？”

“雙葉老師，我實在是聽不懂。”

梓川咲太很爽快的袒露了事實。

“

比如說n等于4的時候答案是11，因為

取起點為2時，你的最多得分是9。其中的一種得分方式是 2→(-2)→4→2→(-4)→(-2);

取起點為3時，你只能得1分，3→(-3);

取起點為4時，你別的轉(zhuǎn)換方式都使用過，因此只能得1分，4→(-4)。

所以最終答案是9+1+1=11,明白了嗎？

”

黑板上已經(jīng)密密麻麻寫了一堆公式，在右下角又寫了一個Accepted。看來雙葉理央已經(jīng)在腦內(nèi)解決了這個問題。

不過對于咲太來說這依舊是一個難題。雖然不是應(yīng)考的范圍，但既然看了這么久，也就順便解答出來吧。

Input

多組輸入輸出。

對于每一組數(shù)據(jù)，輸入一個整數(shù)n(2<=n<=100000)

保證n的個數(shù)小于200,n的總和不超過5000000

Output

對于每一組樣例

輸出梓川咲太最大能夠得到的分數(shù)

Sample Input

Sample Output

C++版本一

預處理一下

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUGusing namespace std; typedef long long ll; const int N=100000+10; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m; ll dp[N]; bool prime(int x){if(n==1) return 0;if(n==2) return 1;for(int i=2;i<=(int)sqrt(x);i++)if(x%i==0) return 0;return 1; } ll sloved(int x){ll ans=0;for(int i=2;i<=(int)sqrt(x);i++){if(x%i==0){ans+=i;if(x/i!=i)ans+=(x/i);}}return ans; } int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endiffor(int i=2;i<=N;i++){if(prime(i))dp[i]=dp[i-1];else{dp[i]=dp[i-1]+sloved(i);}}while(~scanf("%d",&n)){cout <<dp[n]*4+n-1 << endl;}//cout << "Hello world!" << endl;return 0; }

C++版本二

https://www.cnblogs.com/MingSD/p/10050324.html

題解：我們可以從樣例分析中發(fā)現(xiàn)，我們可以經(jīng)過4次跳躍之后返回到原來的這個地方。

也就是說，我們每次走到一個新的位置之后，我們可以遍歷他的所有因子，再返回到這個位置，然后繼續(xù)按原來的路徑行事。

我們不用管他怎么走，只需要明白每出現(xiàn)一個數(shù)會對答案產(chǎn)生什么影響就好了。

最后是 x -> -x 。

#include<bits/stdc++.h> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL mod = (int)1e9+7; const int N = 1e5 + 100; int vis[N]; void init(){for(int i = 2; i < N; ++i){for(int j = i+i, t = 2; j < N; j+=i, t++){vis[j] += t;}} } int main(){init();int n;while(~scanf("%d", &n)){LL sum = 0;for(int i = 2; i <= n; ++i){sum += vis[i];}printf("%lld\n", sum*4+n-1);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的以行走般的速度β的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

速度